Let \(G\) be any undirected graph with positive edge weights, and \(𝑇\) be a…
2025
Let \(G\) be any undirected graph with positive edge weights, and \(𝑇\) be a minimum spanning tree of \(G\). For any two vertices, \(𝑢\) and \(𝑣\), let \(𝑑_1(𝑢, 𝑣)\) and \(𝑑_2(𝑢, 𝑣)\) be the shortest distances between \(u\) and \(𝑣\) in \(G\) and 𝑇, respectively. Which ONE of the options is CORRECT for all possible \(𝐺, 𝑇, 𝑢\) and \(𝑣\)?
- 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)\)
Attempted by 133 students.
Show answer & explanation
Correct answer: B
Claim: For every pair of vertices u and v, d1(u, v) ≤ d2(u, v).
Proof:
The minimum spanning tree T is a subgraph of G, so the unique path in T between u and v is also a path in G.
The length of that path in T equals d2(u, v). Since d1(u, v) is the length of the shortest path in G, we must have d1(u, v) ≤ d2(u, v).
So the correct universal statement is d1(u, v) ≤ d2(u, v).
Example showing strict inequality can occur:
Take three vertices u, v, w with edge weights: u–v = 1, u–w = 2, w–v = 2.
An MST can include edges u–v (1) and u–w (2), leaving out the direct edge w–v. Then d2(w, v) (distance in the tree) = 3, while d1(w, v) (shortest in G) = 2 via the direct edge w–v.
Conclusion: The universally correct relation is d1(u, v) ≤ d2(u, v).