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\)?
Answer
(B)
Explanation
\(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