Correctness

Theorem: KRUSKAL-MST returns a minimum spanning tree.

Proof: By induction (``for'' loop).

• Inductive hypothesis is that T is always a subset of an MST. Since it eventually contains an entire spanning tree, the final result is a minimum spanning tree.
• For the base case, initially, T is empty, and therefore a subset of an MST. Now, consider the processing of an edge (u,v). If u and v are already connected in T, then it can't be part of any MST that contains T, and we toss it out.
• Let's say u and v are not connected. Consider the cut with all the nodes connected to u by T on one side and all other nodes on the other side. This is a cut that doesn't intersect T.
• By the greedy-grow lemma, the smallest edge across the cut can be added to T maintaining the property that T is contained in an MST.
• Claim: (u,v) is the minimum weight edge in the cut. Why?

• Therefore, (u,v) can be added to T en route to an MST.