Correct : b
Answer: B — d1(u,v) ≤ d2(u,v)
Explanation:
The tree T is a subgraph of G. Any path that exists in T also exists in G.
Let P be the shortest path between u and v inside T; its length is d2(u,v).
Since P is also a valid path in G, the shortest distance in G cannot be longer than this path.
Therefore:
d1(u,v) ≤ d2(u,v)
Example:
Graph G is a triangle with vertices A, B, C and edge weights:
AB = 1, BC = 1, AC = 3.
A minimum spanning tree T includes edges AB and BC.
In G: shortest A–C path = A–B–C = 1 + 1 = 2 → d1(A,C) = 2
In T: only path A–B–C = 2 → d2(A,C) = 2
Hence, d1 = d2.
Example
Graph G is a triangle with all edges weight 1: AB = BC = AC = 1.
A minimum spanning tree T includes edges AB and BC.
In G: shortest A–C path = AC = 1 → d1(A,C) = 1
In T: only path A–B–C = 1 + 1 = 2 → d2(A,C) = 2
So d1 < d2.
Conclusion:
Removing edges (as when taking a Minimum Spanning Tree) can never make the distance shorter.
Therefore, the correct option is: B — d1(u,v) ≤ d2(u,v).
Similar Questions
Total Unique Visitors