Question 49

Let $G$ be a connected undirected graph where all edge weights are distinct:

• (A) TRUE: Let $e_1$ be the edge with the smallest weight and $e_2$ be the edge with the second smallest weight. By Kruskal's algorithm, $e_1$ is selected first. Edge $e_2$ cannot form a cycle with $e_1$ alone because a cycle requires at least 3 edges in a simple graph. Thus $e_2$ is always selected.
• (B) TRUE: Consider the edges with the third and fourth smallest weights ($e_3$ and $e_4$). Kruskal's algorithm considers $e_1, e_2, e_3, e_4$ in order. The only way $e_3$ could be rejected is if $e_1, e_2, e_3$ form a 3-cycle ($K_3$). If that happens, $e_1$ and $e_2$ already span those 3 vertices. Edge $e_4$ cannot form a cycle using only $e_1$ and $e_2$ without involving $e_3$. Therefore, $e_4$ must connect to at least one new vertex, so it cannot create a cycle and must be chosen. Thus, at least one of $e_3, e_4$ is always part of the MST.
• (C) TRUE: This is the Cut Property: for any non-trivial partition $(S, V \setminus S)$, the edge of strictly minimum weight crossing the cut must belong to the unique MST.
• (D) FALSE: When all edge weights in a connected graph are distinct, the minimum spanning tree is unique.

Therefore, (A), (B), and (C) are TRUE.