GATE CS 2025 Set 2 Q.10: Analytical and Logical Reasoning

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.

Diagram of a river system with 7 segments (P, Q, R, S, T, U, V) dividing a rectangular land area into 5 zones (Z1, Z2, Z3, Z4, Z5).

Bridges on P, Q, and T

Bridges on P, Q, S, and T

Bridges on Q, R, T, and V

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

Official answer and solution

Official answer: C
From: Official GATE 2025 answer key

Solution

Model the 5 zones as vertices and the 7 river segments as edges connecting adjacent zones; a spanning tree on 5 vertices requires exactly 4 bridges with no cycles.

Treat the 5 zones $Z_1, Z_2, Z_3, Z_4, Z_5$ as vertices of a graph, where each river segment corresponds to a potential bridge (edge) between two zones:

$P$ connects $Z_1$ and $Z_2$
$Q$ connects $Z_1$ and $Z_3$
$R$ connects $Z_2$ and $Z_3$
$S$ connects $Z_1$ and $Z_5$
$T$ connects $Z_3$ and $Z_5$
$U$ connects $Z_4$ and $Z_5$
$V$ connects $Z_3$ and $Z_4$

Connecting $5$ zones with the minimum number of bridges requires a spanning tree of $5 - 1 = 4$ bridges:

(A) has only 3 bridges and leaves $Z_4$ isolated.
(B) has 4 bridges ( $P, Q, S, T$ ), but $Q, S, T$ form a cycle among $Z_1, Z_3, Z_5$ while leaving $Z_4$ disconnected.
(C) places bridges on $Q$ ( $Z_1$ - $Z_3$ ), $R$ ( $Z_2$ - $Z_3$ ), $T$ ( $Z_5$ - $Z_3$ ), and $V$ ( $Z_4$ - $Z_3$ ), connecting all 5 zones via $Z_3$ using the minimum 4 bridges.
(D) uses 5 bridges, which is not the minimum.

Final answer

Option (C)

Common trap

Selecting (B) because it has 4 bridges without checking that zone Z4 (bounded only by U and V) is not connected by P, Q, S, or T.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2025 Computer Science and Information Technology - Session 2 (CS2)
Question: 10 of 65
Section: General Aptitude

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source