GATE CS 2005 Q82a — Graph Traversals (BFS, DFS)

This question is a direct application of the Cut Property of Minimum Spanning Trees (MST).

1. The Cut Property of MSTs

For any undirected graph $G = (V, E)$ with distinct edge weights, let $[X, Y]$ be a partition (cut) of the vertex set $V$. If $e$ is the unique edge of minimum weight that crosses the cut $[X, Y]$ (i.e., has one endpoint in $X$ and the other in $Y$), then $e$ must belong to the Minimum Spanning Tree (MST) of $G$.

Since the graph has distinct positive edge weights, the minimum weight edge $e$ crossing the cut $[X, Y]$ is unique. Therefore, by the Cut Property, $e$ must definitely belong to the MST of $G$. This makes Option A correct.

2. Eliminating Other Options

• Option B (Weighted shortest path from $s$ to $t$): Consider a graph with vertices $V = \{s, a, b, t\}$ partitioned into $X = \{s, a\}$ and $Y = \{b, t\}$. Let the edges and weights be:
  • $(s, b)$ with weight $10$ (crosses cut)
  • $(a, t)$ with weight $100$ (crosses cut)
  • $(a, b)$ with weight $1$ (crosses cut, minimum weight edge $e$)
  • $(s, a)$ with weight $100$
  • $(b, t)$ with weight $100$
  The minimum weight edge crossing the cut is $e = (a, b)$ with weight $1$. However, the shortest path from $s$ to $t$ is $s \to b \to t$ with a total cost of $110$, which does not contain $e = (a, b)$. Thus, Option B is incorrect.
• Option C (Each path from $s$ to $t$): Any path from $s \in X$ to $t \in Y$ must cross the cut $[X, Y]$ at least once, but it can do so using any crossing edge, not necessarily the minimum weight edge $e$. Thus, Option C is incorrect.
• Option D (Weighted longest path from $s$ to $t$): The longest path is unlikely to be forced to use the minimum weight edge. Thus, Option D is incorrect.