Question 50

Evaluate Statement I: 'If $e$ is the lightest edge of some cycle in $G$, then every MST of $G$ includes $e$.'
This statement is FALSE. Consider a graph with vertices $A, B, C, D$:

• Cycle $A-B-C-A$ with edge weights $w(A, B) = 10, w(B, C) = 12, w(A, C) = 14$. Here, $e = (A, B)$ with weight 10 is the lightest edge of this cycle.
• Now add vertex $D$ with edges $w(A, D) = 1$ and $w(D, B) = 2$.
  In the full graph, the MST connects $A, D, B$ using edges $(A, D)$ (1) and $(D, B)$ (2), and connects $C$ using $(B, C)$ (12). The MST edges are $\{(A, D), (D, B), (B, C)\}$, which has total weight $1 + 2 + 12 = 15$.
  Edge $e = (A, B)$ (weight 10) is excluded because in the cycle $A-D-B-A$, $e$ is the heaviest edge ($10 > 1, 2$). Thus, Statement I is FALSE.

Evaluate Statement II: 'If $e$ is the heaviest edge of some cycle in $G$, then every MST of $G$ excludes $e$.'
This is the well-known Cycle Property of MSTs. If an edge $e$ is strictly the heaviest edge in a cycle $C$, then in any spanning tree $T$ containing $e$, removing $e$ partitions $T$ into two disjoint components. Some other edge $e' \in C$ must cross between these two components. Since $w(e') < w(e)$, replacing $e$ with $e'$ creates a spanning tree of strictly smaller weight. Thus, no MST can contain $e$. Statement II is TRUE.

Therefore, Statement II only is true.