GATE2025_CS1_Q18

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 d₁(u, v) and d₂(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?

✅ Final Answer:

The correct option is (B) d₁(u, v) ≤ d₂(u, v).

🔹 Short Answer:

A Minimum Spanning Tree (T) is a subgraph of the original graph (G). The unique path between any two vertices u and v in T is also a valid path in G. The shortest path in G, d₁(u, v), is by definition the path with the minimum possible weight. Since the path from T is one of the candidates for the shortest path in G, d₁(u, v) must be less than or equal to the path distance in T, d₂(u, v).

🔸 Long Answer:

This question explores the fundamental relationship between a graph, its Minimum Spanning Tree (MST), and the concept of shortest paths.

Key Concepts:

• Graph (G): A set of vertices and edges connecting them. In this case, undirected with positive edge weights.
• Minimum Spanning Tree (T): A subgraph of G that connects all vertices together with the minimum possible total edge weight, without forming any cycles.
• Shortest Path d(u, v): The path between vertices u and v with the smallest sum of edge weights. In a tree, the path between any two nodes is unique.

Analysis of the Relationship

Let's break down the logic:

1. T is a Subgraph of G: By definition, every edge and vertex in the MST (T) is also present in the original graph (G).
2. Path in T is also a Path in G: A tree has exactly one unique path between any two vertices. Let's call the unique path between u and v in T as P_T. The length of this path is d₂(u, v). Since T is a subgraph of G, this path P_T is also a valid, legitimate path in G.
3. Definition of Shortest Path in G: The shortest path in G, d₁(u, v), is the path with the minimum possible weight among *all* possible paths between u and v in G.
4. Comparing the Paths: The set of all paths between u and v in G includes the path P_T. Therefore, the shortest path in G can, at best, be equal to the length of P_T, but it can never be greater. It could be smaller if there's a "shortcut" edge in G that was not included in T.

This leads to the conclusion: d₁(u, v) ≤ d₂(u, v).

Example Illustration

• In the example graph G, the shortest path between u and v is the direct edge with weight 4. So, d₁(u, v) = 4.
• The MST T would not include the edge (u,v) of weight 4, because it would form a cycle. It includes edges (u,x) and (x,v).
• In the MST T, the only path from u to v is u → x → v, with a total weight of 2 + 3 = 5. So, d₂(u, v) = 5.
• Here, 4 ≤ 5, which satisfies our condition d₁(u, v) ≤ d₂(u, v).

This demonstrates that the shortest path in the graph is not necessarily the same as the path in the MST, but it can never be longer.

Bibliography:
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms. MIT Press. (Chapter 23: Minimum Spanning Trees & Chapter 24: Single-Source Shortest Paths).

Ask your doubts in comment form our GURUJEE will reply ASAP, click notify me button so that you get notified on reply.