The GATE Grind

GATE 2025 CS (CS2) – Question 10

General Aptitude · Analytical Aptitude: Logical Reasoning and Deduction · 2 marks · Multiple choice

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.

river segments with adjacent zones: P separates Z1|Z2, R separates Z2|Z3, Q separates Z1|Z3, S separates Z1|Z5, T separates Z3|Z5, V separates Z3|Z4, U separates Z4|Z5.
  1. Bridges on P, Q, and T
  2. Bridges on P, Q, S, and T
  3. Bridges on Q, R, T, and V
  4. Bridges on P, Q, S, U, and V

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) Bridges on Q, R, T, and V

Explanation

Connecting 5 zones needs at least 4 bridges forming a spanning tree. Options A and B leave Z4 disconnected, and D uses 5 bridges. Q(Z1-Z3), R(Z2-Z3), T(Z3-Z5), V(Z3-Z4) connect all zones with 4 bridges.