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 d1(u,v) and d2(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, and v?

Question

Accepted Answer

d1(u,v) ≤ d2(u,v). The shortest path distance in the original graph G, denoted as d1(u,v), can be equal to or less than the distance in the minimum spanning tree T, denoted as d2(u,v), because T may not include all edges of G and thus cannot provide a shorter path than the shortest path available in G.

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 d1(u,v) and d2(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, and v?

Solution

Related GATE Technical questions