Kruskal, the Cut Property, and Why Any Minimum Edge Is Safe

Minimum spanning trees have two greedy algorithms, Prim’s and Kruskal’s, that look different and are justified by two properties that turn out to be the same property viewed from opposite sides. Kruskal’s sorts all edges and adds each one that joins two different components. The interesting part is not the sort but the proof that adding an edge never needs to be reconsidered, and the proof is not the usual first-divergence exchange: it is a local argument about cuts.

The problem and the trivial observation

A spanning tree of a connected graph with $n$ vertices and $m$ edges has exactly $n - 1$ edges. If weights are distinct, the minimum spanning tree is unique; if not, several trees may attain the minimum, and every algorithm must produce one of them.

The observation that makes greedy plausible: for any tree $T$ and any edge $e \notin T$, adding $e$ creates exactly one cycle, and removing any edge of that cycle restores a spanning tree. This is the fundamental cycle of $e$ with respect to $T$. Conversely, for any edge $e \in T$, removing it splits $T$ into two components, and any edge of the graph crossing that split reconnects them into a spanning tree. This is the fundamental cut.

Both operations preserve the spanning-tree property and change the total weight by the difference of the two edge weights. So an exchange between a tree and a non-tree edge is always available, and its cost is always computable from the two weights. The only question is which exchange improves.

The cut property

For any subset $S \subset V$ with $S \neq \emptyset$ and $S \neq V$, call the edges with one endpoint in $S$ and one outside a cut. A light edge of the cut is one of minimum weight among the cut’s edges.

Cut property. For any cut, any light edge of the cut belongs to some minimum spanning tree.

Proof: let $e$ be a light edge of the cut $(S, V \setminus S)$, and let $T$ be a minimum spanning tree not containing $e$. Adding $e$ to $T$ creates a cycle, and the cycle must cross the cut an even number of times, so it contains some other edge $f$ crossing the cut. By lightness, $w(e) \le w(f)$. Then $T - f + e$ is a spanning tree with weight no greater than $T$‘s, hence also minimum. So a minimum spanning tree containing $e$ exists.

The argument works for every cut simultaneously, which is what makes it wider in scope than a single exchange. It does not require knowing which tree is optimal; it asserts that the edge is in some optimal tree for any cut it is light for.

Cycle property. The dual statement: for any cycle, an edge of maximum weight on the cycle is absent from some minimum spanning tree, and if the edge weights are distinct it is absent from every one of them. Proof: suppose $T$ contains such an edge $e$. Remove it, splitting $T$; the cycle must contain another edge $f$ crossing that split, with $w(f) \le w(e)$, so $T - e + f$ is a spanning tree of weight at most $T$‘s. If $w(f) < w(e)$ then $T$ was not minimum; if $w(f) = w(e)$ then $T - e + f$ is a minimum tree that avoids $e$. With distinct weights the equality case cannot arise, so no minimum tree contains $e$.

Kruskal as a sequence of cut applications

Kruskal’s algorithm sorts edges by weight and adds an edge if its endpoints are in different components of the forest built so far. The correctness argument identifies the cut at each step.

Suppose the algorithm is about to consider edge $e = (u, v)$ and $u$, $v$ lie in different components of the current forest $F$. Let $S$ be the vertex set of $u$‘s component in $F$. The cut $(S, V \setminus S)$ has $e$ as a crossing edge. Every edge crossing this cut that is strictly lighter than $e$ has already been considered, and each was either added, which would have merged the components, or rejected because its endpoints were already connected. So no crossing edge lighter than $e$ remains unprocessed, and since $e$ is processed in non-decreasing weight order, $e$ is a light edge of the cut. By the cut property, some minimum spanning tree contains $e$. Since $F$ is a subset of that tree by induction, adding $e$ preserves the invariant that $F$ extends to a minimum spanning tree.

When $u$ and $v$ are already connected, $e$ closes a cycle in $F \cup {e}$. All edges of that cycle were added before $e$ and hence have weight at most $w(e)$, so $e$ is a maximum-weight edge of the cycle, and the cycle property says it can be excluded. The rejection is safe.

The two cases are the cut property and the cycle property, applied at every step. This is why Kruskal needs no lookahead and no repair: the invariant “the current forest is a subgraph of some minimum spanning tree” is maintained by each decision, in both branches.

Implementation and the cost of connectivity

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]  # path halving
            x = self.parent[x]
        return x

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        return True

def kruskal(n, edges):
    # edges: list of (weight, u, v)
    dsu = DSU(n)
    total = 0
    used = 0
    for w, u, v in sorted(edges):
        if dsu.union(u, v):
            total += w
            used += 1
            if used == n - 1:
                break
    return total if used == n - 1 else None  # None if disconnected

Sorting is $O(m \log m)$. The union-find operations are $O(m,\alpha(n))$ amortized with union by rank and path compression, where $\alpha$ is the inverse Ackermann function and is at most 4 for any input that fits in memory. The full bound is therefore $O(m \log m)$, dominated by the sort, and the loop stops as soon as $n - 1$ edges have been accepted, so it never scans the remainder of the sorted list once the tree is complete. The structure is the standard disjoint-set forest described in the matroid criterion, where the same independence test appears as a graphic matroid query.

One implementation detail has real consequences: sorting (weight, u, v) tuples compares endpoints on weight ties, which is harmless for the total weight but changes which of several minimum trees is produced. If a downstream consumer expects a canonical tree, the tie-break must be specified, and comparing by vertex index is the usual convention.

Prim’s algorithm and the same cut

Prim’s algorithm grows a single tree from a start vertex, repeatedly adding the lightest edge connecting the tree to a vertex outside it. At each step, the cut is $(S, V \setminus S)$ where $S$ is the current tree’s vertex set, and the chosen edge is by construction the lightest crossing edge. The cut property applies directly, without needing the sort order argument.

The cost differs. With a binary heap the running time is $O(m \log n)$; with a Fibonacci heap it is $O(m + n \log n)$, which is better on dense graphs, where $m$ is close to $n^2$. Kruskal’s cost is the sort of $m$ edges plus near-linear union-find work, so on a sparse graph with $m = O(n)$ the two bounds have the same order and the choice comes down to constants and to which structure fits the implementation. Neither algorithm dominates the other.

Prim’s correctness needs one extra fact that Kruskal’s does not: the invariant is that the current tree is contained in some minimum spanning tree, and this holds because the light edge of the cut from the tree’s vertex set is in some minimum spanning tree by the cut property, and the induction carries it. The subtlety is that the cut changes as the tree grows, so the invariant must be maintained across changing cuts. It works because the cut property is universally quantified over cuts, not because any particular cut is special.

Ties, uniqueness, and the second-best tree

Distinct weights give a unique minimum spanning tree, and the proof is immediate from the cut property: if two trees $T_1 \ne T_2$ both attain the minimum, take an edge $e \in T_1 \setminus T_2$; it is light for the cut induced by removing $e$ from $T_1$, and the cycle property applied to $T_2$ plus $e$ forces a contradiction with distinctness.

With ties, all minimum trees have the same multiset of edge weights. This follows because the sorted weight sequence at which Kruskal adds edges is determined by the weights alone, not by tie-breaking: the number of edges of each weight in any minimum tree is fixed. So the total weight is invariant, but the specific edges are not.

Finding the second-best spanning tree, the minimum-weight spanning tree strictly heavier than the best, is a natural follow-on and uses the same cycle structure. For each non-tree edge $e$, the best tree containing $e$ and otherwise as light as possible is obtained by adding $e$ and removing the heaviest edge on its fundamental cycle. The heaviest edge on each fundamental cycle can be precomputed with a lowest-common-ancestor structure on the tree, and the minimum over all non-tree edges gives the second-best tree in $O(m \log n)$.

A minimum spanning tree also minimizes the heaviest edge among all spanning trees. Let $e$ be the heaviest edge of a minimum spanning tree $T$; removing it splits $T$ into two parts, and any other spanning tree $T’$ must contain some edge $f$ crossing that split. If $f$ were lighter than $e$, replacing $e$ by $f$ would give a lighter spanning tree, so no crossing edge is lighter than $e$; hence $w(e) \le w(f) \le$ (the heaviest edge of $T’$). The converse fails: a tree that minimizes only the heaviest edge need not minimize the total weight.

What the properties do not extend to

The cut property is specific to the objective $\sum w_e$. If the objective is the maximum edge weight instead, every minimum spanning tree is still optimal for it, but the argument is different: the exchange that lowers the total weight may leave the heaviest edge unchanged, so optimality for the bottleneck objective needs a separate cut argument. If the objective involves path lengths, the greedy structure is different and the cut property does not apply; Dijkstra’s algorithm grows a tree of shortest paths, and the edge it adds is the lightest crossing edge by distance from the source, not by edge weight.

Directed graphs break the cut property entirely. The directed minimum spanning arborescence problem, solved by the Chu-Liu/Edmonds algorithm, requires a contraction step that Kruskal’s algorithm has no analogue for, and the greedy edge sort is not optimal. This is a clean illustration that the matroid structure of the graphic matroid is a property of undirected graphs: the independent sets of the directed version do not form a matroid.

One consequence of the cut property is worth carrying into approximation work. Because every minimum spanning tree is also a minimum bottleneck tree, both the tree’s total cost and the weight of its heaviest edge bound an optimal tour from below: a tour contains a spanning tree once any one of its edges is removed, and any spanning tree contains an edge of weight at least that of the minimum spanning tree’s heaviest edge. That is the foundation of the $3/2$ construction in the metric TSP algorithm, which augments a spanning tree rather than a tour. The same tree bound appears in primal-dual treatments of network design, where the cost of the tree the algorithm builds is charged, edge by edge, against the dual variables raised by the ascent.