GATE CS 2007 Q49 — Minimum Spanning Trees

Let us analyze each option to determine which statement is false:

• Option A (TRUE): In Kruskal's algorithm, we sort the edges in non-decreasing order of their weights. Since $e$ has the minimum weight $w$, it can be selected as the very first edge. Since a single edge cannot form a cycle, $e$ will always be part of some Minimum Spanning Tree (MST).
• Option B (TRUE): Let $T$ be an MST that does not contain $e$. Adding $e$ to $T$ creates a unique cycle $C$. For $T$ to be an MST, any edge $e' eq e$ in $C$ must satisfy $weight(e') \le weight(e)$. Since $e$ has the absolute minimum weight $w$ in the entire graph, we also have $weight(e') \ge weight(e) = w$. Thus, $weight(e') = weight(e) = w$ for all edges in the cycle.
• Option C (TRUE): Suppose there exists an MST $T$ containing no edge of weight $w$. If we add an edge $e$ of weight $w$ to $T$, it forms a cycle. Since $T$ contains no edge of weight $w$, all other edges in this cycle must have a weight strictly greater than $w$. Removing any of these heavier edges from the cycle yields a new spanning tree with a strictly smaller weight than $T$, which contradicts the assumption that $T$ is an MST.
• Option D (FALSE): Consider a triangle graph with vertices $A, B, C$ and three edges of equal weight $w$:
  • $e_1 = (A, B)$ with weight $w$
  • $e_2 = (B, C)$ with weight $w$
  • $e_3 = (C, A)$ with weight $w$
  Let $e = e_1$. Any two edges form an MST of total weight $2w$. The tree $T = \{e_2, e_3\}$ is a valid MST, but it does not contain $e$. Therefore, $e$ is not necessarily present in every MST.