GATE 2025 CS1 Q.18: solution and answer

GATE 2025 · CS1Q.18 · 1 mark · 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 $d_{1} (u, v)$ and $d_{2} (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$ ?

(A)
$d_{1} (u, v) = d_{2} (u, v)$
(B)
$d_{1} (u, v) \leq d_{2} (u, v)$
(C)
$d_{1} (u, v) \geq d_{2} (u, v)$
(D)
$d_{1} (u, v) \neq = d_{2} (u, v)$

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

$d_{1} (u, v) \leq d_{2} (u, v)$ holds for all possible $G$ , $T$ , $u$ and $v$ , so option (B) is correct.

Official answer: BSource: Official answer key, GATE 2025 CS1 (IIT Roorkee)

$T$ is a spanning tree of $G$ , so every edge of $T$ is an edge of $G$ with the same weight — $T$ is a subgraph of $G$ on the same vertex set.
Any path between $u$ and $v$ that lies entirely in $T$ therefore also exists in $G$ , using the same edges and hence the same total weight.
So the set of all $u$ - $v$ paths available in $G$ is a superset of the set of all $u$ - $v$ paths available in $T$ (every $T$ -path is also a $G$ -path, and $G$ may additionally have paths that use non-tree edges).
$d_{2} (u, v)$ is the minimum weight over the (smaller) set of $T$ -paths; $d_{1} (u, v)$ is the minimum weight over the (larger or equal) set of $G$ -paths.
Minimizing a quantity over a superset of candidates can never give a larger value than minimizing over a subset of those candidates, since every candidate available to the subset is also available to the superset: $d_{1} (u, v) \leq d_{2} (u, v)$ .
This holds for every choice of $G$ , $T$ , $u$ , $v$ — including cases where $u, v$ are adjacent in $T$ or where $G$ itself is a tree, in which equality $d_{1} (u, v) = d_{2} (u, v)$ happens to hold — but equality is not guaranteed in general (e.g. a shorter path in $G$ can bypass the tree route via non-tree edges), so (A) is not always true, and since $d_{1} \leq d_{2}$ always, $d_{1} > d_{2}$ (needed for (C) alone) and $d_{1} \neq = d_{2}$ (option D) can both fail whenever equality holds.
Hence the only relation guaranteed for all $G, T, u, v$ is $d_{1} (u, v) \leq d_{2} (u, v)$ : option (B).

KEY IDEA

A minimum spanning tree $T$ only removes edges from $G$ ; it never adds a shorter route. So every path available inside $T$ is also available inside $G$ , meaning shortest-path distance can only stay the same or shrink when you move from $T$ to $G$ : $d_{1} (u, v) \leq d_{2} (u, v)$ , always.

WATCH OUT FOR

Assuming a "minimum" spanning tree must preserve shortest-path distances (confusing MST with a shortest-path tree) and picking (A); or reasoning direction backwards and picking (C) by thinking "the tree is smaller so distances in it must be smaller."

From the GATE 2025 CS1 paper. Every question of this paper · Download the full paper · All 28 Graph algorithms questions, with notes

GATE 2025 CS1 Q.18: solution and answer

Answer and solution

More Graph algorithms questions