A town wishes to connect several sites by cables. A cable between two sites has an installation cost, and every site must be reachable from every other site, possibly through intermediate sites. If installation costs are nonnegative, deleting a cycle edge preserves connectivity without increasing cost, so a cheapest connected network can be chosen as a spanning tree. Which cables should be installed? This is different from finding the shortest route between two particular sites: here a single network must connect all sites, and the objective is the sum of the installed edge costs.
Model and optimality by exchange
Let be a finite, connected, undirected graph with at least one vertex. Each edge has a real weight . A spanning tree is a connected, cycle-free subgraph containing every vertex. It has edges, and between any two vertices it contains exactly one path. A minimum spanning tree (MST) minimizes the sum of edge weights among spanning trees. Since a finite connected graph has at least one spanning tree and only finitely many edge subsets, a minimum exists. We do not require distinct or positive weights.
For a nonempty proper subset , the cut consists of edges having one endpoint in and the other outside . A cut respects a forest if no edge of crosses it. An edge is light for a cut if its weight is minimum among all edges crossing that cut; ties are allowed.
Theorem 25.1.1
(Safe-edge theorem)
Suppose a forest is contained in some MST. If a cut respects and is a light edge across that cut, then is contained in some MST.
Proof. Choose an MST containing . If already belongs to , there is nothing to do. Otherwise, add to . The unique path in between the endpoints of , together with , forms a cycle. That path crosses the cut at least once; let be one of its crossing edges. Since the cut respects , is not in . Remove from the cycle. The result is a spanning tree containing , and by lightness. Thus . Since was minimum, equality holds and is also minimum.
Proof X-ray
What the exchange really guarantees
The proof preserves earlier choices because the removed edge crosses a cut respected by . It produces some optimal tree containing the new edge; with tied weights, it does not say that every optimal tree contains it. If is the unique lightest crossing edge, however, the same exchange makes any tree omitting strictly cheaper, so every MST contains .
The related cycle rule runs in the opposite direction. If an edge is strictly heavier than every other edge on a cycle, no MST contains it: removing that edge from a tree containing it separates the tree, and another edge of the cycle reconnects the parts at lower cost. Merely tying for the heaviest is not enough to exclude an edge from every MST. In a triangle with all weights 1, each edge occurs in two of the three MSTs.
Kruskal's algorithm
Sort all edges in nondecreasing order of weight. Start with no edges; scan the sorted list and add an edge precisely when its endpoints are in different components of the current forest. Stop once edges have been chosen, or equivalently scan the whole list. For a one-vertex graph the empty tree is the answer.
Why is a chosen edge safe? Immediately before it is chosen, let be the current component containing one endpoint. No selected edge crosses . The chosen edge crosses it. Every strictly lighter crossing edge has already been scanned. It could not have been rejected because its endpoints were already connected at that earlier time: components only merge, so it would then not cross the present cut. Hence the chosen edge is light for the cut. The safe-edge theorem maintains the invariant that the chosen forest is contained in an MST. By connectivity, the final forest cannot have two components: an edge of would cross between them, and when it was scanned its endpoints could not have already been connected. Therefore the final forest is a spanning tree and, by the invariant, an MST. Ties may be processed in any order.
Counterexample mode
A light edge across an arbitrary cut need not be safe
Claim: a light edge across any cut can be added to a forest contained in an MST. Take the triangle with all weights and the MST forest . The cut does not respect , since crosses it. Its edge is light, yet is the whole triangle, a cycle, so no spanning tree contains it. The repair is the theorem's hypothesis that the cut respects ; Kruskal secures it by taking to be a current component.
A disjoint-set structure can test and merge components efficiently. Sorting dominates the usual implementation at comparisons, with near-linear disjoint-set operations. The correctness proof does not rely on a specific implementation or on a tie-breaking rule.
Worked example 25.1.2
(Build and certify a four-site network)
Let the vertices be , with edges , , , , and . Kruskal accepts and . It rejects , whose endpoints are already connected by . It then accepts and stops with tree of weight .
The cut proof certifies these three choices in sequence: use for , then for , then for . Each chosen edge is light across its stated cut, which respects the previous choices. The edge is strictly heaviest on cycle , so it is excluded from every MST. The same conclusion also follows for from cycle , and for from cycle .
Limits and common mistakes
A shortest-path tree from a selected root minimizes each root-to-vertex path length; an MST minimizes total installed weight. They may differ. For example, with , , and , the root- shortest-path tree uses and has weight 4, whereas either tree using and one of has weight 3. Conversely, an MST need not preserve shortest paths from a root. A disconnected graph has no spanning tree covering all vertices; Kruskal instead produces a minimum spanning forest, one tree per connected component. Negative weights do not invalidate the tree algorithm, because the proof compares weights and never assumes nonnegativity. But if arbitrary connected subgraphs are allowed, extra negative edges can lower their cost: an all-negative triangle costs less with all three edges than with any spanning tree.
Practice
Quick check
(The graph has edges , , , , . Run Kruskal with the triangle edges ordered . Find a different MST and explain why cannot belong to any MST.)
Solution · Answer
Accept , reject , and accept : the weight is 4. Replacing by gives another tree of weight 4. Edge is strictly heaviest on cycle (weights 1, 2, 3), so the cycle rule excludes it from every MST.
Quick check
(Prove that distinct edge weights imply a unique MST. Identify where strict inequality is used.)
Solution · Answer
Suppose distinct MSTs exist, and let be the lightest edge in their symmetric difference, with . Removing divides into two parts. The path between its endpoints contains a crossing edge . By the choice of and distinctness, . Replacing with in yields a strictly cheaper spanning tree, a contradiction.
Quick check
(A student claims that every light edge across a cut belongs to every MST. Give a counterexample, then state a correct version.)
Solution · Answer
In an equal-weight triangle, every edge is light across a cut isolating one endpoint, but any particular edge is omitted by one MST. A light edge can be included in some MST; a unique light edge across a cut belongs to every MST.
Quick check
(A graph has components with edges , , and with edge . Run Kruskal and explain what the result certifies.)
Solution · Answer
Accept , , and ; reject . The result has total weight and is a minimum spanning forest. No spanning tree of the whole graph exists because there is no edge between its two components. The safe-edge proof applies separately to each connected component.