Skip to content
GATEiit

GATE CSE 2025 Session 2 Q10: Fewest bridges to connect five zones split by a river

Question

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.

A rectangular map with river segments P, Q, R, S, T, U and V dividing the land into zones Z1 (lower left), Z2 (upper left), Z3 (top middle), Z4 (right) and Z5 (bottom middle)
Tap the figure to enlarge

Try it: multiple choice: exactly one correct option

Select one option
Wrong answer costs 2/3 mark in GATE.
Show answer and explanation

Answer: C (official GATE 2025 final answer key)

Concept used: Five zones need at least four bridges (a spanning tree); each bridge joins the two zones on either side of its segment.

First step: Note which two zones each segment separates (e.g. R: Z2–Z3, V: Z3–Z4) and find a set of four that links all five zones.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2025 Session 2 CS question paper and final answer key, organised by IIT Roorkee. Question paper · Answer key

More General Aptitude PYQs

PracticePractise General Aptitude questions →Full paperAll GATE CSE 2025 Session 2 questions →