GATE CS 2022 Q39 — Minimum Spanning Trees

Since the graph $G$ is simple, undirected, and has distinct edge weights, it has a unique minimum spanning tree (MST).

Let us analyze each statement:

• Statement A: True
  Let the edges sorted in increasing order of weight be $e_1, e_2, e_3, \dots$. Using Kruskal's algorithm, we first select $e_1$. The second edge $e_2$ cannot form a cycle with $e_1$ because a cycle in a simple graph requires at least 3 edges. Thus, the edge with the second smallest weight ($e_2$) is always included in the MST.
• Statement B: True
  Let the sorted edges be $e_1, e_2, e_3, e_4, \dots$. We know $e_1$ and $e_2$ are always selected.
  The third edge $e_3$ can only be rejected if it forms a cycle with the already selected edges, which means $e_1, e_2, e_3$ must form a triangle.
  If $e_3$ is rejected, the set of selected edges remains $\{e_1, e_2\}$. Now, the fourth edge $e_4$ cannot form a cycle with $\{e_1, e_2\}$ because a cycle requires at least 3 edges. Thus, if $e_3$ is rejected, $e_4$ must be accepted. Therefore, at least one of $e_3$ or $e_4$ (or both) must be part of the MST.
• Statement C: True
  This is the standard Cut Property of MSTs. For any cut $(S, V \setminus S)$ of a graph, the minimum-weight edge crossing the cut (the light edge) must belong to the MST. Since all edge weights are distinct, this light edge is unique and is always part of the unique MST.
• Statement D: False
  A graph with distinct edge weights always has a unique minimum spanning tree.