GATE CS 2025 Set 2 Q10 — General Aptitude

To connect the $5$ land zones ($Z1, Z2, Z3, Z4, Z5$), we can model the zones as vertices and the river segments as potential edges (bridges) in a graph.

1. Minimum Bridges Required: To connect $n = 5$ distinct vertices, any connected graph must have at least $n - 1 = 4$ edges (bridges). This immediately eliminates Option A, which proposes only $3$ bridges ($P, Q, T$).
2. Least Number of Bridges: Since we want the least number of bridges, a $4$-bridge configuration is preferred over a $5$-bridge configuration. This makes Option D ($5$ bridges) non-optimal if a valid $4$-bridge solution exists.
3. Verifying the 4-Bridge Options:
   • If we place bridges on the segments in Option B ($P, Q, S, T$), they fail to connect all $5$ zones (creating a cycle or leaving at least one zone completely isolated).
   • Placing bridges on the segments in Option C ($Q, R, T, V$) successfully connects all $5$ zones without forming any redundant cycles, thereby forming a spanning tree.

Thus, the correct option is C.