IAE Academy

GATE 2025 IN GA Q.10: solution and answer

GATE 2025 · INGA Q.10 · 2 marks · MCQ

The diagram below shows a river system consisting of 7 segments, marked P, Q, R, S, T, U, and V. It splits the land into 5 zones, marked Z1, Z2, Z3, Z4, and Z5. We need to connect these zones using the least number of bridges. Out of the following options, which one is correct?

Note: The figure shown is representative.

GATE 2025 IN GA question 10: A rectangle (the land) crossed by thick dark curved lines (the river), with three junction points roughly along a…Tap to open full size
Figure from the GATE 2025 IN paper. It is part of the question.
Figure description

A rectangle (the land) crossed by thick dark curved lines (the river), with three junction points roughly along a horizontal line near the middle. Junction J1 is left of centre, junction J2 is at the centre, junction J3 is right of centre. Segment P runs from the left edge of the rectangle, slightly below mid-height, rightwards to J1. Segment R runs from J1 up and to the right, curving to leave through the top edge slightly right of centre. Segment Q runs roughly horizontally from J1 to J2, dipping slightly. Segment S runs from J2 down and to the left, leaving through the bottom edge left of centre. Segment T runs roughly horizontally from J2 to J3. Segment V runs from J3 up and to the right, leaving through the right edge near the top. Segment U runs from J3 down and to the right, leaving through the right edge near the bottom. Zone labels: Z2 in the top-left region (above P, left of R); Z3 in the top-middle region (right of R, above Q and T, left of and above V); Z4 on the right between V (above) and U (below); Z5 in the bottom-middle region (right of S, below T, left of and below U); Z1 in the bottom-left region (below P and Q, left of S). Segment letters are printed beside their segments: P above the left part of P, R to the right of R, Q below Q, T above T, V left of V, U left of U, S right of S.

  1. (A)

    Bridges on P, Q, and T

  2. (B)

    Bridges on P, Q, S, and T

  3. (C)

    Bridges on Q, R, T, and V

  4. (D)

    Bridges on P, Q, S, U, and V

Answer and solution

ANSWER

Option (C): bridges on Q, R, T and V join Z3 to Z1, Z2, Z5 and Z4. That connects all five zones with the minimum of bridges and no cycle.

Official answer: CSource: Official answer key, GATE 2025 IN (IIT Roorkee)

  1. Read off which two zones each river segment separates. A bridge on a segment joins exactly those two zones: P: Z1–Z2, R: Z2–Z3, Q: Z1–Z3, S: Z1–Z5, T: Z3–Z5, V: Z3–Z4, U: Z4–Z5.

  2. Model the land as a graph. The zones are vertices and the bridges are edges, so there are 5 vertices and 7 possible edges.

  3. Minimum count: joining vertices takes at least edges, and exactly is enough only when those edges form no cycle (a spanning tree). Here that is bridges.

  4. (A) P, Q, T has only 3 bridges, fewer than 4, so it cannot connect all 5 zones. It joins Z1, Z2, Z3 and Z5 and leaves Z4 isolated. Rejected.

  5. (B) P (Z1–Z2), Q (Z1–Z3), S (Z1–Z5), T (Z3–Z5). Q, S and T form the cycle Z1–Z3–Z5–Z1, so one bridge is wasted, and no chosen bridge touches Z4, which stays cut off. Rejected.

  6. (D) P (Z1–Z2), Q (Z1–Z3), S (Z1–Z5), U (Z4–Z5), V (Z3–Z4). This does connect every zone, but it uses 5 bridges, and 5 edges on 5 vertices must contain a cycle (here Z1–Z3–Z4–Z5–Z1). Since 4 bridges are enough, it is not the least number. Rejected.

  7. (C) Q (Z1–Z3), R (Z2–Z3), T (Z3–Z5), V (Z3–Z4). Every bridge has Z3 at one end and reaches one of the other four zones, so all 5 zones are connected with 4 bridges and no cycle. That is a spanning tree, which uses the minimum of 4.

  8. Hence option (C) connects all the zones with the least number of bridges.

KEY IDEA

Treat the zones as vertices and the bridges as edges. Joining zones with the fewest bridges means a spanning tree: exactly bridges that reach every zone and form no cycle. For 5 zones that is 4 bridges, so check every option for all three conditions: the count, reaching every zone, and having no cycle.

WATCH OUT FOR

Choosing (B) because it has the right number of bridges (4) without checking that it reaches Z4. Q, S and T form a loop, so one bridge is wasted. The other trap is choosing (D) because it does connect every zone, even though it uses 5 bridges when 4 are enough.

From the GATE 2025 IN paper. Every question of this paper · Download the full paper · All 41 Reasoning questions, with notes

More Reasoning questions