Minimum Spanning Trees and the Cut Property

A minimum spanning tree is the cheapest set of edges that connects every vertex of an undirected weighted graph, and one rule, the cut property, says which edges are safe to put in it. This card defines both, shows the rule on the topic's graph, and gives the argument for why it holds. Kruskal's algorithm and Prim's algorithm are both built on it.

In an undirected graph an edge joins its two ends both ways, and each edge carries a weight, such as the cost of a cable. A spanning tree of a connected graph is a set of its edges that reaches every vertex and contains no cycle; with V vertices it always has exactly V − 1 edges, since each edge after the first vertex brings in one more. A minimum spanning tree is a spanning tree whose weights add up to the least.

A cut splits the vertices into two groups, neither empty, and an edge crosses the cut when its ends are in different groups. The diagram below draws the topic's graph, six vertices and nine edges, with the cut that puts A, B and C on one side and D, E and F on the other.

The cut property says: for any cut, the lightest edge crossing it belongs to some minimum spanning tree, and when no two weights are equal, as here, to the only one. Three edges cross this cut, and the lightest is B-D at 5. A run listed every spanning tree of the graph, 55 of them; the least total is 17, only one tree has it, and that tree is A-C, B-C, B-D, D-E and E-F. B-D is in it.

The argument is an exchange, the same kind of proof as Proving a Greedy Choice With an Exchange Argument. Take a minimum spanning tree that leaves out the lightest crossing edge, call it e. Adding e to the tree closes exactly one cycle. That cycle crosses the cut by e, and to get back to where it started it must cross again by some other edge, f. Removing f leaves every vertex still connected with V − 1 edges, so the result is a spanning tree too. Its total changed by e's weight minus f's weight, which is 0 or less because e is the lightest edge crossing. So a tree containing e costs no more, and e is safe to add.

The property does not say that a crossing edge is safe because it cannot close a cycle, or that only the lightest edge in the whole graph is safe. Any cut works, and the lightest edge across it is the safe one. Kruskal's algorithm and Prim's algorithm differ only in which cut they look at each time.

Picture islands linked by bridges, where the council pays for as few and as cheap bridges as will let anyone reach any island. The picture breaks once islanders care about their own journey: they would pay more for a shorter commute, and the tree counts only the total. Reading Shortest Paths From a Minimum Spanning Tree shows what that costs.

Reach for a minimum spanning tree when a problem asks to connect every site for the least total cost, with costs that run both ways: cable between offices, pipes between buildings, roads between villages.