The cut property

Kruskal and Prim look different, but one fact makes both of them right. It is called the cut property, and its proof is an exchange argument of the kind GRDY-2 taught.

Cuts and crossing edges

A cut splits the vertices into two non-empty sides, S and the rest. An edge crosses the cut when one end is in S and the other is not. Every spanning tree has at least one edge across every cut: otherwise nothing would join the two sides.

Step through the first variant of the figure. Each step picks a side, marks the crossing edges, and takes the cheapest. After six cuts the six edges form a cheapest tree.

The exchange proof

Let e be a cheapest edge crossing the cut, and T a cheapest spanning tree. If T contains e, there is nothing to prove. If not:

1. Add e to T. In a tree, this closes exactly one loop: e and the tree path between its ends (lesson 1).
2. e goes from one side of the cut to the other, and the tree path comes back. So the loop crosses the cut at least once more, at some tree edge f.
3. Remove f. The loop is broken in one place, so everything stays joined: T − f + e is a spanning tree.
4. f also crosses the cut, and e is a cheapest crossing edge, so w(e) ≤ w(f). The new tree costs w(T) − w(f) + w(e) ≤ w(T). T was cheapest, so the new tree is cheapest too, and it contains e.

The second variant of the figure steps through this exchange on a tree that is not the cheapest; the swap still never makes it more expensive. The proof also works when the cut must avoid edges chosen before: if no chosen edge crosses the cut, f is not one of them, so the new tree keeps every chosen edge.

Why Kruskal and Prim are right

Both keep the invariant “the chosen edges are part of some cheapest tree”, and each step uses the cut property with a well-chosen cut that no chosen edge crosses.

• Prim. The cut is the tree so far against everything else. No tree edge crosses it, and Prim takes the cheapest edge that leaves the tree, which is the cheapest crossing edge.
• Kruskal. When Kruskal keeps u–v, take the cut between u’s group and everything else. No kept edge crosses it, because groups are joined only by kept edges. Every cheaper edge was looked at earlier and either kept or skipped; a skipped edge lies inside one group. So no cheaper edge crosses this cut, and u–v is a cheapest crossing edge.

By induction the V − 1 chosen edges are part of some cheapest spanning tree, and a spanning tree has exactly V − 1 edges, so they are a cheapest spanning tree. The proofs only compare costs with each other, which is why only the order of the costs matters and negative costs are fine.

Ties, and which edges can appear

• All costs different. Then the cheapest tree is unique. If two cheapest trees T and T′ differed, take the cheapest edge e that is in one but not the other, say in T. Adding e to T′ closes a loop, and that loop has an edge f not in T (T has no loop). f is more expensive than e, because e was the cheapest edge in just one tree and costs are all different. Swapping f for e makes T′ cheaper, which is impossible.
• Which edges can appear. An edge u–v of cost w is in some cheapest tree exactly when u and v are not already joined by edges that all cost less than w. If they are joined that way, the edge is strictly the most expensive on a loop (cycle property). If they are not, the cut between “everything joined to u by cheaper edges” and the rest has u–v as a cheapest crossing edge (cut property). Kruskal’s method, run one cost at a time, answers this for every edge at once: SPAN-P4.
• Edges in every cheapest tree. An edge is in all of them when, among the edges of the same cost, removing it would disconnect the groups formed by cheaper edges: it is a bridge in that graph. Finding bridges is CONN-3.
• The same sorted order. Every cheapest tree has the same list of costs when sorted. So any question about the costs (the most expensive edge in the tree, the sum of the k cheapest) has the same answer for every cheapest tree.

Now try SPAN-P4, Lines in some cheapest tree.