GATE CS 2026 Set 1 Q39 — Minimum Spanning Trees

Since the graph $G$ has unique edge weights, it has a unique Minimum Spanning Tree (MST).

• Option A is True (Cycle Property): For any cycle $C$ in $G$, the edge with the strictly largest weight in $C$ cannot belong to any MST. If it did, removing it would disconnect the MST into two components, which could then be reconnected using a lighter edge from the same cycle, resulting in a spanning tree of strictly smaller weight.
• Option B is False: Consider a cycle $A-B-C-A$ with edge weights $w(A,B) = 3$, $w(B,C) = 4$, and $w(C,A) = 5$. Let there be an additional vertex $D$ with edges $w(A,D) = 1$ and $w(D,B) = 2$. The unique MST of this graph consists of the edges $\{(A,D), (D,B), (B,C)\}$. The edge $(A,B)$ is the smallest edge in the cycle $A-B-C-A$, but it is not in the MST.
• Option C is False: Consider a simple path graph $A \xrightarrow{1} B \xrightarrow{2} C$. The unique MST must contain both edges. For vertex $B$, the incident edges are $(A,B)$ and $(B,C)$. The largest weight incident edge is $(B,C)$, which is present in the MST.
• Option D is True (Cut Property): For any vertex $v \in V$, consider the cut $(S, V \setminus S)$ where $S = \{v\}$. The edges crossing this cut are precisely the edges incident on $v$. By the Cut Property, the minimum-weight edge crossing any cut must belong to the MST. Therefore, the edge with the smallest weight incident on $v$ is always in the MST.