A strong answer
The key fact is the cut property: for any split of the vertices into two nonempty sides, a lightest edge crossing the split belongs to some minimum spanning tree.
Proof by exchange: take an MST T that doesn't contain the lightest crossing edge e. Adding e to T creates a cycle, and because e crosses the split, the cycle crosses back through another edge f. Remove f: the result is still a spanning tree, and since w(e) ≤ w(f), its weight is at most T's. So some MST contains e.
Kruskal sorts edges ascending and takes each edge that joins two different components. When it takes u–v, consider the cut between u's current component and the rest of the graph. Every lighter edge was examined earlier and either taken, so it lies inside some component, or skipped because both endpoints were already together. Either way, no lighter edge crosses this cut, so u–v is a lightest crossing edge and safe. Induction over the steps shows the edges taken so far are always contained in some MST, and after n − 1 edges they are one.
Skipped edges are justified by the cycle property: the heaviest edge on any cycle is not needed in an MST, and an edge that closes a cycle among already-taken, lighter edges is the heaviest on that cycle. Cost is O(E log E) for the sort plus near-linear union-find work. With distinct weights, the MST is unique.
What the interviewer is listening for
- A precise statement of the cut property.
- The exchange argument, adding e and removing f.
- Connecting it to Kruskal's specific choice, with the right cut.
Common mistakes
- Saying "greedy works because we always take the cheapest edge" with no argument.
- Choosing a cut that some lighter, untaken edge crosses.
- Claiming the MST is always unique.