GATE CS 2026 Set 1 — Question 49

For a simple undirected graph with unique edge weights, the Minimum Spanning Tree (MST) is unique.Statement (A) is True: This is known as the Cycle Property of MSTs. For any cycle $C$ in the graph, the edge with the strictly largest weight in $C$ cannot be part of any MST. If it were, we could remove it and replace it with any other edge from the cycle to create a spanning tree with a smaller total weight, contradicting the definition of an MST.Statement (B) is False: There is no general property that the smallest edge in a cycle must be in the MST. For example, if the vertices of a cycle are connected by even smaller edges outside of that cycle, the smallest edge within the cycle might still be redundant and excluded from the MST.Statement (C) is False: Consider a graph with only two vertices $u$ and $v$ connected by a single edge $(u, v)$. For vertex $u$, this edge is the largest (and only) incident edge, and it must be in the MST to ensure connectivity.Statement (D) is True: This follows from the Cut Property. For any vertex $v$, the set of edges incident on $v$ forms a cut separating $v$ from the rest of the graph ($V \setminus \{v\}$). The minimum weight edge crossing any cut must be part of every MST. Here, the minimum weight edge crossing this specific cut is the edge with the smallest weight incident on $v$.