Let šŗ be any undirected graph with positive edge weights, and š‘‡ be a minimum spanning tree of šŗ. For any two vertices, š‘¢ and š‘£, let š‘‘1 (š‘¢, š‘£) and š‘‘2 (š‘¢, š‘£) be the shortest distances between š‘¢ and š‘£ in šŗ and š‘‡, respectively. Which ONE of the options is CORRECT for all possible šŗ, š‘‡, š‘¢ and š‘£?

A.

dā‚(u, v) = dā‚‚(u, v)

B.

d1 (u, v) ≤ d2 (u, v)

C.

d1 (u, v) ≥ d2 (u, v)

D.

š‘‘1 (š‘¢, š‘£) ≠ š‘‘2 (š‘¢, š‘£)

Solution:

• In G, the shortest path between u and v might use edges that ae not in T.
• In MST T, the only available path is unique path, so the MST path might be longer than the shortest path in G, but it can never be shorter.

Ex: 

MST for the above graph is

The shortest path in G d1 (u, v) = 5 but in MST d2 (u, v) = 6.