GateAI
Minimum Spanning Trees

GATE CSE 2025 Set 1 · Q18

MCQ1 markEasy

Time

Let GG be any undirected graph with positive edge weights, and TT be a minimum spanning tree of GG. For any two vertices, uu and vv, let d1(u,v)d_1(u, v) and d2(u,v)d_2(u, v) be the shortest distances between uu and vv in GG and TT, respectively. Which ONE of the options is CORRECT for all possible GG, TT, uu and vv?

Select one answerSingle correct

Pick an option to check

Solution

Step-by-step verified solution

Official answer: B) d1(u, v) ≤ d2(u, v)

Minimum Spanning Trees

Since TT is a spanning tree of GG, the edge set of TT is a subset of the edge set of GG, i.e., E(T)⊆E(G)E(T) \subseteq E(G).

  • The path between any two vertices uu and vv in TT is also a valid path between uu and vv in GG.

  • The shortest distance d1(u,v)d_1(u, v) in GG is the minimum weight across all possible paths between uu and vv in GG.

  • Because all paths in TT are contained in GG, the minimum path length in GG can never exceed the path length in TT.

Therefore, for all possible graphs GG, spanning trees TT, and pairs of vertices u,vu, v, we always have:

d1(u,v)≤d2(u,v)d_1(u, v) \leq d_2(u, v)

Hence, (B) is the correct option.

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 Minimum Spanning Trees previous year question is Q18 of the GATE CSE 2025 Set 1 paper. Find more GATE CSE PYQs on Minimum Spanning Trees in Algorithms, 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 Minimum Spanning Trees 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.

Minimum Spanning Trees in GATE CSE

Minimum Spanning Trees has 13 GATE CSE PYQs across 9 papers from 2011 to 2026. 2 of them are 1-mark MCQs like this one, and it is the only one in GATE CSE 2025 Set 1.

How GATE tests Minimum Spanning Trees

More from GATE CSE 2025 Set 1

Share this solution

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

GateAI solution cardGATE CSE 2025 Set 1 · Q18 · MCQ

Let G be any undirected graph with positive edge weights, and T be a minimum spanning tree of G. For any two vertices, u and v, let d1(u, v) and d2(u, v) be the shortest distances between u and v in G and T, respectively. Which ONE of the options is CORRECT for all possible G, T, u and v?

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.