From a local choice to a global tree
A network may offer many ways to connect all its vertices. The problem differs from finding shortest paths from one source: a tree is charged once per selected edge, not once for each route that uses it.
Definition 4.1.1
(Spanning tree, minimum spanning tree and crossing edge)
Assume a finite, connected, undirected loopless multigraph with vertices and edges. Parallel edges are distinct and may have equal weights. Edge weights are arbitrary finite real numbers, including zero and negative values. A spanning tree connects every vertex without a cycle, so it has edges; its weight is the sum of its edge weights. A minimum spanning tree minimizes this sum. For a vertex set with , an edge crosses the cut when exactly one endpoint lies in . We count weight comparisons as constant-cost operations. For , the empty edge set is a spanning tree of weight zero.
The algorithm
Sort the edges by nondecreasing weight, breaking ties in any fixed order. Begin with an empty set . Scan the sorted list: add the current edge if its endpoints are in different connected components of ; otherwise skip it. When the scan ends, output .
Proposition 4.1.2
(The output is a spanning tree)
For a connected input, the set returned by the scan is a spanning tree.
Proof
(No cycle, and no gap between components)
The chosen edges never form a cycle, because each new edge joins two different components. The final forest must connect all vertices: otherwise, since the input is connected, a path of original edges between two final components contains an edge crossing from one final component to another, and that edge could not have been skipped when scanned, since its endpoints were then in different components. A connected forest is a tree, so it has edges.
Lemma 4.1.3
(Cut exchange)
Let be contained in some minimum spanning tree , and let be a vertex set with such that no edge of crosses . If is a lightest edge among all edges crossing this cut, then is contained in some minimum spanning tree.
Proof
(Swap a heavier crossing edge for e)
If , keep . Otherwise adding to creates a unique cycle. A cycle crosses a cut an even number of times and is one crossing, so the cycle contains another crossing edge , and . No edge of crosses the cut, so . Since is lightest among crossing edges, . Removing from breaks the only cycle, leaving a connected graph with edges, that is, a spanning tree . It contains , and its weight is . Since is minimum, so is .
Theorem 4.1.4
(Kruskal's greedy guarantee)
For every connected input satisfying the assumptions, the algorithm returns a minimum-weight spanning tree. Ties and negative weights do not invalidate the guarantee.
The exchange invariant
Proof
(Each selected edge is a lightest crossing edge)
Maintain the invariant that some minimum spanning tree contains every edge already in . It holds initially, because a finite connected graph has a minimum spanning tree. Suppose the algorithm is about to add , whose endpoints lie in different components of . Let be the component containing one endpoint. No edge of crosses , since is a component.
The edge is a lightest crossing edge. If another crossing edge came earlier in the sorted order, its endpoints were already in different components when it was scanned, because components only merge and are still separated before adding . It would therefore have been selected, contradicting the fact that no edge of crosses the cut. So every crossing edge comes at or after in the order and weighs at least , ties included. The cut exchange lemma shows that the invariant is preserved. Skipped edges leave unchanged.
At termination is itself a spanning tree and lies inside some minimum spanning tree. Two spanning trees on the same vertex set each have edges, so they are equal. This proves optimality, not just that the output is a tree.
Proof X-ray
Why the next crossing edge is safe
The non-obvious move is the exchange: instead of arguing about every spanning tree, take one optimum tree that already contains and repair it locally. Each hypothesis has a job. Connectivity of the input and a cut with an edge of across it guarantee that the cycle created by contains a second crossing edge . The fact that is a component of is what keeps outside , so the swap does not damage the edges already chosen. The sorted scan is what makes lightest among crossing edges, and the inequality needs only , so ties are harmless.
Nothing in the argument adds, subtracts or scales weights, only compares them, which is why negative weights are allowed. The proof closes because each step keeps one optimum tree around and the final has edges, leaving no room for it to differ from that tree. If were merely some crossing edge rather than a lightest one, the swap could increase the weight and the invariant would fail.
A worked scan
Worked example 4.1.5
(A tie and a skipped edge)
Let the edges be of weight , and of weight , of weight , and of weight . Suppose the tie orders before . Select and ; skip because it would close the triangle; then select . The resulting tree has weight . If the equal-weight edges are scanned in the opposite order, is selected and skipped, giving a different minimum tree of the same weight. The exchange proof covers either tie order.
Worked example 4.1.6
(Parallel edges and a negative weight)
Take vertices with two parallel edges between and of weights and , an edge of weight and an edge of weight . The sorted list is the edge, , , then the edge. Select the edge, joining and . Select , joining to that component. Skip , since and are already connected, and skip the parallel edge. The tree has two edges and weight . The other four spanning trees have weights , , and , all larger.
Worked example 4.1.7
(A disconnected input gives only a forest)
Take four vertices with only the edges of weight and of weight . The scan selects both, ending with edges where a spanning tree would need . The output is a minimum spanning forest, with weight , but no spanning tree of the whole graph exists, so the guarantee above does not apply.
Counterexample mode
The cheapest edges alone may form a cycle
Consider a triangle on with all three edges of weight , plus edge of weight . The three cheapest edges form a cycle and leave disconnected, although three edges is the right count for four vertices. A spanning tree must take and only two triangle edges, for weight . Sorting by weight is useful only together with the component test, which skips the third triangle edge and then selects .
Common mistake
(Expecting a unique answer when weights tie)
In the first worked scan the two orders of and give two different minimum spanning trees, and , both of weight . A tie-breaking rule decides which tree is output, but not whether it is optimal. Only when all weights are distinct is the minimum spanning tree unique.
Common mistake
(Removing or shifting negative weights first)
Because shortest-path methods may need nonnegative weights, it is tempting to add a constant to every edge here. That is unnecessary: the proof only compares weights. For a triangle with weights the algorithm selects and directly, and no adjustment is needed. For spanning trees, adding the same constant to every edge changes every tree's weight by exactly , so the optimal tree is the same, but this is an observation about spanning trees, not a requirement of the algorithm.
Implementation and boundary cases
One simple implementation labels each vertex with its current component. To merge two labels, scan all vertices and replace one label by the other. A test costs and a merge costs , so sorting and the scan use operations in this comparison model. Faster component data structures require their own analysis. The proof above does not depend on a particular implementation.
If the input is disconnected, the same scan returns a forest, but no spanning tree of the whole graph exists. Check connectivity, or check whether the final forest has edges, before making a spanning-tree claim. A forest of edges on vertices is connected. Negative edges may be selected and do not create an unbounded objective: a finite graph has finitely many spanning trees.
Exercises
Quick check
(Run the worked scan with before . Give the selected edges and total weight.)
Skip any edge that closes a cycle.
Solution · Answer
Select , and , and skip and . The total is .
Quick check
(A triangle has edge weights . Find a minimum spanning tree and its weight.)
A spanning tree of a triangle has two edges.
Solution · Answer
Select the edges of weights and , yielding a tree of weight . The exchange argument remains valid for negative weights.
Quick check
(Why can a selected edge and a different crossing edge of equal weight both be compatible with some optimum?)
Look at the inequality the exchange proof needs.
Solution · Answer
The exchange proof needs , not strict inequality. Swapping equal-weight edges can preserve optimal total weight; the choices need not produce a unique tree.
Quick check
(A graph has four vertices and the scan ends with two selected edges. Can it have a spanning tree? Why?)
How many edges would a spanning tree have, and what does the scan do on a connected input?
Solution · Answer
No. The chosen edges form a forest. If the input were connected, the scan would produce a spanning tree with three edges, so ending with two certifies disconnection.