GATE CS 2000 Q2.18 — Minimum Spanning Trees

Since the graph $G$ has distinct edge weights, it has a unique minimum spanning tree (MST). Let's analyze each statement to find the false one:

• Statement A (True): By the cut property of MSTs, the edge with the absolute minimum weight ($e_{min}$) in a connected graph must belong to every MST.
• Statement B (True): If $e_{max}$ is part of the MST, it cannot belong to any cycle in $G$. If it did, we could remove $e_{max}$ and connect the tree using another edge from the cycle (which must have a smaller weight than $e_{max}$ since $e_{max}$ is the maximum weight edge in $G$). This would yield a spanning tree of smaller weight, contradicting the minimality of the MST. Thus, $e_{max}$ must be a bridge (cut-edge), meaning its removal disconnects $G$.
• Statement C (False): If $G$ itself is a tree (e.g., a simple path graph), then the unique MST of $G$ is $G$ itself, which must contain $e_{max}$. Therefore, the claim that no MST contains $e_{max}$ is false.
• Statement D (True): A connected graph with distinct edge weights always has a unique MST.

Thus, statement C is the false statement.