Motivation
To connect several sites, one may choose a set of undirected links whose total cost is as small as possible. A route that is cheapest from one chosen site to each other site need not give the cheapest network overall. The network problem asks for one shared collection of edges and counts each selected edge once.
Two greedy algorithms build such a network in different orders. Kruskal scans all edges by weight; Prim grows one connected region at a time. Both need the same underlying explanation: a light edge crossing a suitable cut can be exchanged into an optimum without increasing its cost. The word “suitable” matters when edges have equal weights or some edges have already been chosen.
Definitions and scope
Definition 5.4.1
(Spanning forests and minimum spanning forests)
Let be a finite undirected multigraph with vertices and edge identities. Parallel edges and loops are allowed. Every edge has a finite real weight; weights may be negative, zero or equal. A spanning forest contains all vertices and restricts to a spanning tree on each connected component of . Isolated vertices contribute singleton trees and no edges. A minimum spanning forest has the least total edge weight among these forests. When is connected and nonempty, it is a minimum spanning tree (MST). For , the empty forest has total weight zero; we do not call the empty graph connected.
Definition 5.4.2
(Cuts, crossing edges and respect)
A cut is specified by a nonempty proper vertex set and its complement. An edge crosses the cut if it has one endpoint on each side. A cut respects a forest if no edge of crosses it. A loop never crosses a cut and cannot belong to a forest. A cycle may have two distinct parallel edges; whenever a cycle or edge is mentioned, its edge identity matters.
A finite graph has a spanning forest, for example by taking a spanning tree of each component. There are only finitely many edge subsets, so at least one minimum spanning forest exists. This existence argument also permits arbitrary finite real weights; no nonnegativity is needed.
Theorem 5.4.3
(Safe light edge across a respecting cut)
Suppose a forest is contained in some minimum spanning forest. If a cut respects and an edge is of minimum weight among all edges crossing that cut, then some minimum spanning forest contains . Ties are allowed; the claim is existence of an optimum containing the selected edge, not that every optimum contains it.
Cut exchange proof
Proof
(Exchange along the cycle created by )
Choose an optimum forest containing . If already belongs to , there is nothing to do. Otherwise the endpoints of belong to one original connected component, and the corresponding tree in has a unique path between them. That path must cross the cut. Adding creates a cycle consisting of and the path; among its other edges choose a crossing edge .
Because the cut respects , the edge is not in . Removing breaks the cycle and leaves a spanning tree of that original component, with every other component unchanged. Since is a lightest crossing edge, . The new spanning forest contains and has weight no larger than the optimum . It is therefore also optimal. This proof handles parallel edges and equal weights; it never assumes a unique optimum.
Proof X-ray
The old choices must survive the exchange
The proof makes one swap, and each hypothesis controls a different property of the new forest. That the endpoints of lie on opposite sides of the cut forces the -path between them to contain a crossing edge ; this is where the cut itself is used. Removing an edge of the cycle formed by and that path keeps the component connected and acyclic, so the result is again a spanning forest; this needs only that lies on the cycle.
Lightness of among crossing edges gives , so the cost does not rise. Finally, the respecting condition guarantees , so every earlier choice survives the swap. Without that last property the swap might delete an edge of , and the induction used by Kruskal and Prim would lose its invariant. Equal weights only turn a strict improvement into a non-increase, which is all the conclusion needs.
Theorem 5.4.4
(Cycle exclusion and ties)
If an edge is strictly heavier than every other edge of a cycle, it belongs to no minimum spanning forest. More generally, an edge of maximum weight on a cycle can be omitted by at least one minimum spanning forest, even if there are ties.
Proof
(Replace the cycle edge by a crossing edge)
For either statement, suppose an optimum contains the specified cycle edge . Removing separates its tree into two sides. The rest of the original cycle has an edge crossing this separation. It is not already in that tree, since a tree has no other edge across the separation after removing . Replacing by again gives a spanning forest. If is strictly heavier, the total cost falls, a contradiction. If is merely a maximum, the replacement is no heavier and hence is another optimum omitting . A tied maximum may still appear in a different optimum.
Kruskal: grow a forest in weight order
Sort all edge identities by nondecreasing weight, with any consistent tie order. Start with no selected edges. Scan the sorted edges; select an edge exactly when its endpoints are in different components of the selected forest. Discard loops automatically. Continue until every edge has been considered.
Theorem 5.4.5
(Correctness of Kruskal's algorithm)
For every finite weighted multigraph and every fixed tie order, the edges selected by Kruskal's algorithm form a minimum spanning forest.
Proof
(The selected forest stays inside an optimum)
The selected edges remain acyclic, since an edge joining different forest components cannot close a cycle. Before accepting an edge , use the vertex set of one endpoint's current forest component as . The cut respects the selected forest. Every lighter edge crossing it was scanned earlier; it could not have been rejected then, because components only merge and its endpoints are still separated now. Therefore no lighter crossing edge exists, and is a lightest crossing edge. The cut theorem extends the invariant that the selected forest lies inside some optimum.
When the scan ends, no original edge joins two distinct selected-forest components: such an edge would have been selected when examined or its endpoints would already have merged. Hence the selected forest spans each original component. Since it is contained in an optimum forest and already spans each component, it is itself an optimum.
A disjoint-set structure supports the component tests. With union by size and no path compression, every parent chain has length : whenever a root is attached below another root, its component size at least doubles. Comparison sorting and these operations give comparisons and index operations, with storage including the input. Faster disjoint-set bounds require their own analysis. The count assumes exact, constant-cost comparison of weights; arbitrary binary representations have their own bit cost.
Concept lensStructural
Forests as the independent sets of a matroid
Call an edge set independent when it contains no cycle (loops excluded). Subsets of forests are forests. If and are forests with , then has fewer components on the same vertex set, so some edge of joins two components of and can be added to . These two properties make the forests the independent sets of a matroid, whose maximal members are exactly the spanning forests. Kruskal is the matroid greedy algorithm, and the augmentation step is the exchange argument above.
Prim: grow one region, then restart
In one original connected component, choose any starting vertex. Let be its currently reached vertices and let be the selected edges. While an edge crosses from to the rest, add a minimum-weight crossing edge and its outside endpoint. The selected edges remain a tree on , and the cut respects them. The exchange theorem maintains an optimum containing all choices. No crossing edge remains exactly when is the whole original component.
For a disconnected graph, restart at any vertex not yet reached and apply the same rule in its component. The union of the resulting trees is a spanning forest contained in an optimum, hence itself minimum. Isolated vertices require no edge. Ties may be broken arbitrarily and can produce different valid forests.
For a simple implementation, maintain at each unreached vertex its cheapest known incident edge from the current reached region. An array scan selects the smallest finite key; when none exists, restart at an unreached vertex. Inspect outgoing adjacency entries of each newly reached vertex once. Across the entire graph, initialization and scans cost and edge inspections , with storage including the graph. The keys are individual crossing-edge weights, not path lengths. Infinity is a separate “no candidate” flag; negative edges pose no difficulty.
A certificate for an entire proposed forest
Theorem 5.4.6
(Path-maximum optimality criterion)
Let be a spanning forest of . It is minimum if and only if, for every nonloop edge outside , its weight is at least the maximum weight on the unique -path between its endpoints.
Proof
(One swap for necessity, repeated exchange for sufficiency)
Necessity follows by adding an outside edge . If it were lighter than some path edge, replacing that path edge by would produce a cheaper spanning forest. This is valid with parallel edges; loops are excluded because their endpoints have an empty path and they cannot improve a forest.
For sufficiency, let the displayed inequalities hold and take any spanning forest . If it differs from , choose . Remove from its tree in to split that original component into two parts. Adding to creates a cycle whose remaining path must cross this split; choose such an edge on the path. No edge of other than crosses the split, so . The -path between the endpoints of contains , and the hypothesis gives . Replacing by in does not increase weight and increases the number of shared edges with . Repeat finitely many times until the forest is . Therefore weighs no more than any competitor and is minimum.
This is a checkable characterization, not automatically a linear-time verifier. A direct implementation can first check the spanning-forest property, then traverse a tree path for each outside edge; this uses elementary operations in a straightforward adjacency-list model. Faster path-maximum data structures are a separate algorithmic task. The criterion remains valid for negative weights: take the actual maximum on each nonempty path, rather than initializing it to zero.
Worked examples
Worked example 5.4.7
(Different selection orders, one optimum)
Take vertices with edge weights , , , and . Kruskal selects , then , then , for total . Starting Prim at selects , then , then , with the same total. Kruskal's first edge need not touch Prim's starting vertex, and negative weights are allowed.
Worked example 5.4.8
(Equal weights admit several trees)
In a four-cycle with all four edges of weight one, deleting any one edge gives an MST of weight three. A chosen edge is light across some cut, but need not occur in every optimum. If a diagonal of weight two is added, it is uniquely heaviest on either triangle containing it and belongs to no MST.
Worked example 5.4.9
(Disconnected graph and parallel edges)
Let have two parallel edges of weights and , let be isolated, and let have a loop of weight . The minimum spanning forest uses the edge, includes as a singleton, and ignores both the loop and the heavier parallel edge. Its total is . A negative loop is not allowed merely because it would lower an unconstrained edge sum.
Counterexample mode
A shortest-path tree need not minimize network weight
Take a triangle with weights , and . Direct edges from to both vertices give shortest paths and total tree weight four. A minimum spanning tree uses and either one of the two weight-two edges, for total three. Its path from to the other endpoint has cost three, so it is not a shortest-path tree from .
Common mistakes and scope
Common mistake
(A lightest cut edge need not be in every optimum)
Do not conclude that every lightest cut edge is in every optimum when ties occur. In a four-cycle with all weights one, every edge is a lightest edge across some cut, yet each edge is missing from the spanning tree obtained by deleting it.
Common mistake
(A cut that does not respect the earlier choices)
Do not replace the respecting-cut condition by an arbitrary cut while claiming all previous choices remain. In the triangle with and , the forest lies in the minimum spanning tree . The cut does not respect , and is a lightest edge crossing it, yet has weight while every minimum spanning tree has weight .
Common mistake
(Running Prim once on disconnected input)
On disconnected input, an algorithm that starts Prim only once produces a tree for one component, not a spanning forest of the whole graph. A loop also cannot be chosen, even when its weight is negative: it never crosses a cut, so Prim never meets it as a candidate.
The weight comparisons above are exact. These results do not claim floating-point robustness, a particular heap implementation, or a shortest-path guarantee. The example of a network optimized by total edge weight has a different objective from the one-source distance problem.
Summary
The cut exchange lemma safely extends a partial optimum, while a strictly heavy cycle edge is forbidden. Kruskal and restarted Prim use those ideas in different orders and both produce minimum spanning forests. The path-maximum test gives an independent optimality characterization, with the cost of implementing that test stated separately.
Exercises
Quick check
(For the weighted graph in the first example, run Kruskal and Prim starting at . State their selected edges and total weight.)
Solution · Answer
Kruskal selects , , in that order; Prim from selects , , . Both obtain total . At each Prim step the next edge is minimum across the current reached cut, even though the newly exposed edge is negative.
Quick check
(A triangle has weights one, two and two. Find all of its MSTs and explain what the cycle rule does and does not imply about either weight-two edge.)
Solution · Answer
Each MST consists of the weight-one edge and exactly one of the two weight-two edges, for total three. Each weight-two edge is absent from some MST but present in another. Neither is strictly heavier than all other cycle edges, so the strict exclusion rule applies to neither.
Quick check
(A triangle has weights , and . Is the tree with edges and minimum? Use the path-maximum test and give a cheaper tree if it fails.)
Solution · Answer
The tree path from to uses of weight and of weight . Its maximum is , but the outside edge has weight , which is smaller. The criterion fails; replacing with gives a tree of weight instead of . Initializing the path maximum to zero would give a wrong value on this all-negative path.
Quick check
(A graph has two nontrivial connected components of sizes three and two, and one isolated vertex. How many edges must a spanning forest contain? Explain how restarted Prim handles the isolated vertex.)
Solution · Answer
A tree on three vertices has two edges, one on two vertices has one, and an isolated vertex has none. Every spanning forest therefore has three edges. When Prim restarts at the isolated vertex, there is no crossing edge, so that singleton component is complete immediately.