GateAI
Analytical Aptitude

GATE CSE 2025 Set 2 · Q10

MCQ2 marksMedium

Time

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 CSE 2025 Set 2 Q10 diagram

Select one answerSingle correct

Pick an option to check

Solution

Step-by-step verified solution

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

Analytical Aptitude

To connect 55 disconnected land zones (Z1,Z2,Z3,Z4,Z5Z_1, Z_2, Z_3, Z_4, Z_5), the minimum number of bridges required is 5−1=45 - 1 = 4 (forming a spanning tree of the zone adjacency graph).

Let us determine which zones are separated by each river segment:

  • P separates Z1Z_1 and Z2Z_2

  • R separates Z2Z_2 and Z3Z_3

  • Q separates Z1Z_1 and Z3Z_3

  • S separates Z1Z_1 and Z5Z_5

  • T separates Z3Z_3 and Z5Z_5

  • V separates Z3Z_3 and Z4Z_4

  • U separates Z4Z_4 and Z5Z_5

Now evaluating the options:

  • (A) Bridges on P, Q, and T: Uses only 33 bridges, which is insufficient to connect 55 zones.

  • (B) Bridges on P, Q, S, and T: Connects {Z1,Z2,Z3,Z5}\{Z_1, Z_2, Z_3, Z_5\}, leaving Z4Z_4 completely disconnected.

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

    • Q connects Z1Z_1 and Z3Z_3

    • R connects Z2Z_2 and Z3Z_3

    • T connects Z5Z_5 and Z3Z_3

    • V connects Z4Z_4 and Z3Z_3

    This forms a star graph centered at Z3Z_3, connecting all 55 zones with exactly 44 bridges (the minimum possible).

  • (D) Bridges on P, Q, S, U, and V: Uses 55 bridges, which is not the least number of bridges.

Therefore, option (C) is correct.

Try the question first, then check your work.

Think the official key or this write-up is wrong?

Report error or challenge

Examiner trap

The misconception this question tests

This Analytical Aptitude previous year question is Q10 of the GATE CSE 2025 Set 2 paper. Find more GATE CSE PYQs on Analytical Aptitude in General Aptitude, or browse all GATE CSE PYQs.

Free diagnostic

Where do you stand for GATE?

Take the 20-minute diagnostic: the 3 topics that cost you the most marks, and a rank range. Or sit 5 related Analytical Aptitude PYQs now with no account.

One GATE CSE PYQ every morning

An official question by email at 7 AM IST, with a link to its verified solution. Unsubscribe in one click.

Analytical Aptitude in GATE CSE

Analytical Aptitude has 11 GATE CSE PYQs across 8 papers from 2017 to 2026. 7 of them are 2-mark MCQs like this one, and it is the only one in GATE CSE 2025 Set 2.

How GATE tests Analytical Aptitude

More from GATE CSE 2025 Set 2

Share this solution

A plain-text card for WhatsApp or Telegram study groups.

GateAI solution cardGATE CSE 2025 Set 2 · Q10 · 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.

Topic-wise GATE CS PYQs with verified steps

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.