GATE CS 2025 Set 1 | Question 18
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\)?
Explanation
Answer: (B)
\(T\) is a subgraph of \(G\), so every path between \(u\) and \(v\) in \(T\) is also a path in \(G\). Hence the shortest path in \(G\) can never be longer than the one in \(T\): \(d_1(u, v) \le d_2(u, v)\).
Equality is not guaranteed. Take a triangle \(x, y, z\) with \(w(x, y) = w(y, z) = 1\) and \(w(x, z) = 1.5\); the MST keeps the two edges of weight 1. Then \(d_1(x, z) = 1.5\) but \(d_2(x, z) = 2\), which rules out (A) and (C), while \(d_1(x, y) = d_2(x, y) = 1\) rules out (D).
Answer: B