Why Kruskal's Algorithm Is Correct

The Correctness Question

Kruskal’s algorithm processes the edges of a weighted graph in nondecreasing order of weight. It accepts an edge when its endpoints lie in different components of the forest built so far, and rejects it otherwise. Sorting and applying this rule produces a candidate tree, but correctness requires more than showing that the final edges connect the vertices without a cycle. We must also show that their total weight is as small as possible.

Throughout this tutorial, \(G=(V,E)\) is a finite, connected, undirected simple graph with at least one vertex, and each edge \(e\in E\) has a real weight \(w(e)\). A spanning tree is a connected, acyclic subgraph containing every vertex. A minimum spanning tree (MST) is a spanning tree of minimum total edge weight among all spanning trees of \(G\). Negative weights and ties are allowed.

The key invariant is that after each acceptance, the current forest is contained in at least one MST. It does not claim that every MST contains those edges, or that the MST is unique. Instead, it ensures that the decisions made so far can still be completed optimally.

The Cut Used at an Acceptance

A cut is a partition \((S,V\setminus S)\) of the vertex set into two nonempty parts. An edge crosses the cut if one endpoint lies in each part. The cut respects a forest \(F\) if no edge of \(F\) crosses it. A light edge across a cut is an edge of minimum weight among the edges crossing that cut.

Proof. If \(e\in T\), then \(T\) already contains \(F\) and \(e\), as required. Otherwise, adding \(e\) to the tree \(T\) creates a cycle: the endpoints of \(e\) already have a unique path between them in \(T\), and that path together with \(e\) forms the cycle. Since \(e\) crosses the cut, this cycle includes a crossing edge \(f\) on the path in \(T\). The cut respects \(F\), so \(f\notin F\). Because \(e\) is light, \(w(e)\le w(f)\). Removing \(f\) from the cycle leaves a spanning tree \(T'=T+e-f\) containing \(F\) and \(e\), and its weight satisfies \(w(T')=w(T)+w(e)-w(f)\le w(T)\). Since \(T\) is minimum, \(T'\) cannot have smaller weight than \(T\); therefore it is also an MST. \(\square\)

This exchange argument is the cut property in the form needed here. The special cut for Kruskal comes from the forest’s current components. If the algorithm accepts \(e=uv\), let \(C\) be the component of \(F\) containing \(u\). The cut \((C,V\setminus C)\) respects \(F\), and \(e\) crosses it because \(v\notin C\).

Why the Accepted Edge Is Light

Proof. Let \(F\) be the current forest, let \(C\) be the component containing one endpoint of \(e\), and use the cut \((C,V\setminus C)\). The edge \(e\) crosses this cut. Suppose there were a crossing edge \(f\) with \(w(f)<w(e)\). Since Kruskal processes edges in nondecreasing order, \(f\) was processed before \(e\). If \(f\) was accepted, its endpoints are still connected by edges of the current forest, because accepted edges are never removed. If \(f\) was rejected, its endpoints were already connected by accepted edges when it was processed, and those edges also remain in the current forest. Either way, the endpoints of \(f\) belong to the same current component. This contradicts the fact that \(f\) crosses \((C,V\setminus C)\). Thus no crossing edge has weight strictly less than \(w(e)\), so \(e\) is light. \(\square\)

The argument uses a strict inequality to rule out a lighter crossing edge. It does not require \(e\) to be the unique lightest edge: other crossing edges may have the same weight. This is why the proof applies regardless of how ties are resolved.

The Correctness Theorem

Proof. We prove by induction on the number of accepted edges that the current forest \(F\) is contained in some MST. Initially, \(F=\varnothing\). A connected finite graph has a spanning tree: repeatedly delete an edge from any cycle while preserving connectivity, until no cycle remains. There are finitely many spanning trees, so one has minimum weight. Thus an MST exists, and it contains the empty forest.

Now suppose the invariant holds before an edge \(e\) is accepted. By the induction hypothesis, choose an MST \(T\) containing \(F\). Let \(C\) be the current component containing one endpoint of \(e\). The cut \((C,V\setminus C)\) respects \(F\), because no edge of \(F\) joins distinct components. By the preceding lemma, \(e\) is light across this cut. The cut-exchange lemma therefore gives an MST containing \(F\) and \(e\). This proves the invariant after the acceptance. Rejected edges do not change \(F\), so they do not affect the invariant.

It remains to show that the final forest is a spanning tree. It is acyclic because an edge is added only when its endpoints are in different components. If the final forest had at least two components, connectedness of \(G\) would give an edge joining two of them: take a path in \(G\) between vertices in distinct components and consider the first edge on that path that leaves one component. Its endpoints would still be in distinct final components, so they were in distinct components when that edge was processed as well, since components only merge. Kruskal would have accepted it, a contradiction. Thus the final forest is connected and acyclic, hence a spanning tree. The invariant says it is contained in an MST; since both are spanning trees, they have the same edges. Therefore the algorithm’s output is an MST. For a single vertex, the algorithm accepts no edges and returns the empty spanning tree, so the conclusion also holds in that case. \(\square\)

Tracing the Invariant in Examples

Common Mistake and Why the Proof Matters

Wrong calculation: In the first example, one might take the first three edges in the sorted list, \(12,23,13\), and report weight \(1+2+3=6\) as the beginning of the answer. But those three edges form a cycle on \(\{1,2,3\}\); they do not connect vertex \(4\) or vertex \(5\), so they cannot be part of a forest built by Kruskal’s rule. The correction is to reject \(13\), whose endpoints are already connected, and continue to \(34\) and \(45\). The result is a spanning tree of weight \(12\).

Another error is to assume that every edge processed by Kruskal belongs to every MST. The proof establishes a more precise statement: after each accepted edge, there exists an MST containing all edges accepted so far. When weights tie, there may be several MSTs, and the algorithm’s chosen edge need not appear in all of them. What matters is that the cut exchange preserves at least one optimal completion.

For a disconnected graph, the same reasoning applies within each connected component, and Kruskal returns a minimum spanning forest. The connectedness hypothesis is needed for the conclusion that the output is one spanning tree; without it, no spanning tree of the whole graph exists.