Minimum Spanning Trees and the Cut Property

Let $G = (V, E)$ be a connected, undirected graph with a weight function $w: E \to \mathbb{R}$ assigning a real-valued cost to each edge. A spanning tree of $G$ is a subgraph $T$ that is connected, contains all vertices in $V$, and has no cycles. Because a tree on $n$ vertices always has exactly $n - 1$ edges, every spanning tree of $G$ has exactly $|V| - 1$ edges — removing any one edge disconnects it, and adding any edge not in $T$ creates exactly one cycle. A minimum spanning tree is a spanning tree $T^*$ such that

is minimum among all spanning trees of $G$. If edge weights are distinct, the MST is unique; if weights can tie, there may be several MSTs, all sharing the same total weight. A cut of $G$ is any partition of $V$ into two nonempty, disjoint sets $S$ and $V \setminus S$. An edge $(u, v)$ crosses the cut if one endpoint is in $S$ and the other is in $V \setminus S$. A cut is said to respect a set of edges $A$ if no edge in $A$ crosses it — every edge of $A$ lies entirely inside $S$ or entirely inside $V \setminus S$. An edge is a light edge crossing a cut if it has the minimum weight among all edges crossing that cut (ties allowed — there may be several light edges). The central theorem of MST theory, the cut property, states: for any cut that respects some subset $A$ of edges belonging to some MST, if $(u,v)$ is a light edge crossing that cut, then $(u,v)$ is safe for $A$ — meaning $A \cup \{(u,v)\}$ is still a subset of some minimum spanning tree. This single fact is the engine behind every correct greedy MST algorithm: it says you never have to look at the whole graph to make a locally optimal, globally safe choice. A companion fact, the cycle property, gives the dual guarantee: on any cycle, the maximum-weight edge (assuming it is not tied for lightest) is never required in any MST, and can safely be excluded from consideration.

The cut property is proved using an exchange argument, the standard technique for showing greedy choices are optimal. The proof itself is the mechanism: it shows precisely how to transform any MST that disagrees with the greedy choice into one that agrees, without increasing total weight.

Theorem (Cut Property). Let $A$ be a subset of some minimum spanning tree of $G$. Let $(S, V\setminus S)$ be any cut that respects $A$ (no edge of $A$ crosses it). Let $(u,v)$ be a light edge crossing the cut. Then $A \cup \{(u,v)\}$ is a subset of some minimum spanning tree of $G$. Proof sketch. Let $T$ be a minimum spanning tree with $A \subseteq T$ — such a $T$ exists by hypothesis. If $(u,v) \in T$, we are already done. Otherwise, since $T$ is a spanning tree, adding $(u,v)$ to $T$ creates exactly one cycle $C$ (because $T$ was acyclic and connected, and $(u,v)$ joins two vertices already connected by a unique tree path). Since $u \in S$ and $v \in V \setminus S$, and the tree path from $u$ to $v$ inside $T$ must also cross from $S$ to $V \setminus S$ at least once, there is some other edge $(x,y) \in T$ that also crosses the cut $(S, V \setminus S)$. Because $(u,v)$ is a light edge crossing the cut, $w(u,v) \le w(x,y)$. Form

Removing $(x,y)$ from $T$ splits it into two components exactly along the same cut structure that $(x,y)$ bridged; adding $(u,v)$ reconnects them, since $(u,v)$ also crosses that same cut. So $T'$ is again a spanning tree. Its weight satisfies

so $T'$ is also a minimum spanning tree (it cannot weigh less than $T$ since $T$ was already minimum, so equality holds, meaning $w(u,v) = w(x,y)$). Crucially, $(x,y) \notin A$ because the cut respects $A$ and $(x,y)$ crosses the cut, so removing it does not disturb $A$. Thus $A \subseteq T'$ and $(u,v) \in T'$, giving $A \cup \{(u,v)\} \subseteq T'$, a minimum spanning tree. $\blacksquare$ This proof is constructive: it doesn't just assert existence, it shows the exact swap — trade the crossing tree edge $(x,y)$ for the light edge $(u,v)$ — that repairs any MST into one containing the greedy choice. The generic greedy algorithm packages this theorem into a template: maintain a set $A$ of edges that is always a subset of some MST (an invariant), and repeatedly find any safe edge to add, using the cut property to certify safety, until $A$ itself is a spanning tree. ``` GENERIC-MST(G, w): A ← empty set while A does not form a spanning tree of G: find a cut (S, V \ S) that respects A let (u, v) be a light edge crossing that cut A ← A ∪ {(u, v)} return A ``` Every step is licensed directly by the cut property: as long as the chosen cut respects the current $A$, the light edge crossing it is guaranteed safe, so $A$ remains a subset of some MST throughout. When the loop ends, $A$ is a spanning tree that is a subset of some MST — and a spanning tree that is a subset of an MST must equal that MST, since both have exactly $|V|-1$ edges. This template does not specify how to find a good cut efficiently — that choice is exactly what distinguishes Kruskal's Algorithm (which processes edges globally in sorted order, using each edge's endpoints' components as an implicit cut) from Prim's Algorithm (which grows a single tree and always cuts around its current vertex set).

The generic greedy algorithm's correctness follows directly by induction from the cut property, and its complexity depends entirely on how cuts and light edges are found — the template itself is not an efficient algorithm.

Correctness (invariant argument). Claim: at every point in the loop, $A$ is a subset of some MST. This is trivially true initially, since $A = \emptyset$ is a subset of any MST. Suppose it holds before an iteration. The algorithm picks a cut respecting $A$ (guaranteed to exist as long as $A$ is not yet a spanning tree — take $S$ to be the vertex set reachable using only edges in $A$ from any vertex, and $V \setminus S$ the rest; no edge of $A$ can cross this cut by definition of reachability) and adds a light edge $(u,v)$ crossing it. By the cut property, $A \cup \{(u,v)\}$ is again a subset of some MST. The invariant is preserved by induction. When the loop terminates, $A$ is both a spanning tree (loop condition) and a subset of some MST, and since any spanning tree subset of a $(V-1)$-edge MST must itself have $V-1$ edges to span all vertices, $A$ equals that MST exactly.

Termination. Each iteration strictly increases $|A|$ by one (a new edge is added, since the chosen cut respects $A$, meaning no edge of $A$ crosses it, so the light edge across it cannot already be in $A$). Since $|A|$ is bounded above by $V - 1$, the loop terminates after exactly $V-1$ iterations.

Complexity, honestly stated. The generic template above is a proof device, not a runnable efficient algorithm: "find a cut that respects $A$, then find a light edge crossing it" is left unspecified and, done naively, could cost $O(V + E)$ per iteration just to determine reachability and scan all crossing edges, giving $O(V(V+E))$ overall — far from optimal. The real payoff of the cut property is that it licenses two very different efficient specializations:

• Kruskal's Algorithm sorts all edges once, $O(E \log E)$, and uses a union-find structure to test whether each edge connects two different components (an implicit cut), running in $O(E \log E)$ overall.
• Prim's Algorithm maintains one growing tree and always cuts around its current vertex set, using a priority queue to extract the light edge in $O(\log V)$ time per step, running in $O(E \log V)$ with a binary heap.

Both achieve the same guarantee — total weight equal to the true minimum — because both are just efficient implementations of "always add a safe edge," and safety is certified by the same theorem. Space is $O(V + E)$ for any adjacency-list-based implementation, dominated by storing the graph itself, consistent with Graph Representations: Adjacency Lists and Matrices.

Tradeoffs. The cut property gives a clean, greedy, provably optimal algorithm — unlike many optimization problems (e.g. the traveling salesman problem) where greedy choices are only heuristic. The tradeoff is that MST greediness relies crucially on the tree structure: for edge-weighted problems requiring cycles (shortest paths with negative weights, or Steiner trees connecting only a subset of vertices), no analogous exchange argument holds, and greedy strategies can fail badly. MST theory is a rare case where a hard-looking combinatorial optimization is solved exactly by simple local rules.

Consider six towns $A, B, C, D, E, F$ with the weighted edges below (matching the diagram above).

We trace the generic greedy algorithm using a sequence of hand-picked cuts, each respecting the current $A$, each time taking the light edge crossing it.

After step 5, $A = \{$A–D, A–B, D–E, E–F, B–C$\}$ has 5 edges spanning all 6 vertices — the loop terminates. Total weight is $2+4+5+3+6 = 20$. Notice the algorithm never needed the edges A–C (7), C–D (9), or C–F (12); by the cycle property, C–D is the maximum-weight edge on the cycle A–D–C–A (weights 2, 9, 7), so it can never be required, matching what greedy selection independently discovered. This trace also shows that the specific cuts chosen above are arbitrary — different valid choices of $S$ at each step (or running Kruskal's Algorithm instead, which sorts globally: 2, 3, 4, 5, 6, 7, 9, 12 and skips any edge closing a cycle) would still land on the same total weight of 20, since edge weights here happen to be distinct, making the MST unique.

The minimum spanning tree problem has one of the earliest documented "correct greedy algorithm" success stories in combinatorial optimization, predating modern computer science by decades. Its clean theoretical foundation — the cut property — turned an intuitively plausible heuristic into a rigorously provable method, a pattern that later became a template for greedy-algorithm design generally.

MST computation underlies real network design tasks directly: telecommunications and cable-television companies use MST-style optimization to lay physical infrastructure at minimum wiring cost, and electrical grid planning descends conceptually from Borůvka's original motivation. Circuit design and VLSI layout tools use MST-based heuristics to minimize wire length when routing connections between components on a chip. In computational biology, MSTs help build phylogenetic trees and cluster gene-expression data, since "connect everything at minimum total distance" is exactly the abstract problem biologists face when grouping similar samples. In machine learning, single-linkage hierarchical clustering is essentially the successive merging steps of Kruskal's algorithm, and MSTs are used as subroutines in approximation algorithms for harder problems like the traveling salesman problem and Steiner tree problem, where an MST gives a provably good lower bound. Network reliability analysis and image segmentation (treating pixels as a weighted graph and cutting expensive edges) both lean on the cut property directly, since deciding which connections are "essential" versus "redundant" is precisely what an MST formalizes. Any system that must reduce redundant, costly connections while preserving full reachability — from routing protocols to power distribution networks — is, underneath, solving a minimum spanning tree problem, and every such solver's correctness ultimately traces back to the cut property proved here.

Ask the tutor: How exactly do Kruskal's and Prim's algorithms each implement "find a respecting cut and its light edge" efficiently, and why do they arrive at the same total weight despite exploring completely different cuts?