Computer Sciences > GATE 2025 SET-1 > Graph Theory
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, u and v?
A
d1(u,v)=d2(u,v)
B
d1(u,v)≤d2(u,v)
C
d1(u,v)≥d2(u,v)
D
d1(u,v)≠d2(u,v)

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

Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time on Depth First Search of G? Assume that the graph is represen...
#14 MCQ
Let G=(V,E) be a directed graph where V is the set of vertices and E the set of edges. Then which one of the following graphs has the same strongly connected co...
#18 MCQ
In an adjacency list representation of an undirected simple graph G = (V, E), each edge (u, v) has two adjacency list entries: [v] in the adjacency list of u, a...
#91 MCQ

Related Topics

No tags found

Unique Visitor Count

Total Unique Visitors

Loading......