GATE 2022 CS Q.49: solution and answer

Official answer: A, B, CSource: Official answer key, GATE 2022 CS (IIT Kharagpur)

1. Since all edge weights are distinct, Kruskal's algorithm produces the (unique) MST: at every step it either accepts the next-cheapest edge (if it joins two different components) or rejects it (if it would close a cycle), and because weights are distinct there is never a tie to break arbitrarily.

2. (A): Let $e_1$ be the globally smallest edge, with endpoints $u_1,v_1$; Kruskal always accepts it, merging $\{u_1\}$ and $\{v_1\}$ into one component. When the second-smallest edge $e_2$ is considered, the only pair of vertices lying in the same component is $\{u_1,v_1\}$ itself. Since $G$ is simple, no edge other than $e_1$ can join $u_1$ and $v_1$, so $e_2\ne e_1$ cannot close a cycle at this stage. Hence Kruskal always accepts $e_2$: (A) is TRUE.

3. (B): By the same argument as above, $e_1$ and $e_2$ are always both accepted. Two cases arise for the components they create. Case 1 — $e_1,e_2$ are vertex-disjoint: the only same-component vertex pairs are $\{u_1,v_1\}$ and $\{u_2,v_2\}$, each already realized by $e_1$ or $e_2$; so $e_3$ (being a different edge) cannot close a cycle and is always accepted, satisfying the statement. Case 2 — $e_1,e_2$ share a vertex, say $e_1=(A,B)$, $e_2=(A,C)$, forming a 3-vertex component: among $A,B,C$ the only edge not yet placed is $BC$, and it is the unique edge whose acceptance could ever be blocked by this component (its weight rank is necessarily $\ge 3$, since ranks 1 and 2 are already $e_1,e_2$). If $BC=e_3$, it is rejected (it would close the triangle) — but then all three possible edges among $\{A,B,C\}$ have been accounted for, so $e_4$ cannot lie inside this component and must be accepted. If $BC\ne e_3$ (its rank is $\ge 4$ or the edge doesn't even exist in $G$), then $e_3$ itself cannot close this cycle and is accepted. Either way, at least one of $e_3,e_4$ is always accepted into the MST: (B) is TRUE.

4. (C): This is exactly the cut property of MSTs — for any nontrivial vertex partition $(S,V\setminus S)$, the minimum-weight edge crossing the cut lies in every MST. Since all weights are distinct, adding any other crossing edge before this one is impossible without first using it (any cycle created by a heavier crossing edge could be broken by removing a heavier edge on the cycle, and the minimum crossing edge is never that heavier edge), so it is always selected by Kruskal/Prim. (C) is TRUE.

5. (D): Distinct edge weights mean Kruskal's algorithm has no tie to break at any step, so the sequence of accept/reject decisions — and hence the MST itself — is completely determined. Therefore $G$ has exactly one MST, not multiple: (D) is FALSE.