Minimum spanning trees & the cut property

The minimum-spanning-tree problem

Given a connected, undirected graph $G=(V,E)$ with a real weight $w(u,v)$ on each edge, a *spanning tree* is an acyclic subset $T\subseteq E$ that connects all the vertices. A minimum spanning tree (MST) is a spanning tree of minimum total weight $w(T)=\sum_{(u,v)\in T} w(u,v)$. This models any "connect everything as cheaply as possible" problem: lay cable to every building, wire a circuit, build roads between cities.

The solution is always a *tree* for two reasons. It must span — touch all $|V|$ vertices — and it must be acyclic: a cycle would contain a removable edge whose deletion keeps the graph connected but lowers the weight, so no minimum solution has one. A connected acyclic graph on $|V|$ vertices has exactly $|V|-1$ edges, so every MST has exactly $|V|-1$ edges.

MSTs are not necessarily unique — if two edges tie in weight, swapping one for the other can give a second MST with the same total.

Growing an MST one safe edge at a time

Both classic algorithms follow a generic greedy template. Start with $A=\varnothing$ and keep the loop invariant: *$A$ is a subset of some MST*. At each step add a safe edge — an edge $(u,v)$ such that $A\cup\{(u,v)\}$ is still a subset of some MST. After $|V|-1$ safe additions, $A$ is an MST. The whole game is: *how do you know an edge is safe?*

The cut property (Theorem 21.1) — the one MST theorem

First, the vocabulary:

- A cut $(S,V-S)$ is a partition of the vertices into two sides. - An edge crosses the cut if its endpoints are on different sides. - The cut respects $A$ if *no* edge of $A$ crosses it. - A light edge crossing a cut is a minimum-weight edge among all edges crossing it.

Theorem (cut property). Let $A$ be a subset of some MST, let $(S,V-S)$ be any cut that respects $A$, and let $(u,v)$ be a light edge crossing that cut. Then $(u,v)$ is safe for $A$.

Worked proof (the exchange / cut-and-paste argument). Let $T$ be an MST containing $A$. If $(u,v)\in T$ we are done. Otherwise, adding $(u,v)$ to $T$ creates a cycle; that cycle crosses the cut an even number of times, so it contains some *other* crossing edge $(x,y)\in T$. Because the cut respects $A$, $(x,y)\notin A$. Form $$T' = T - \{(x,y)\} \cup \{(u,v)\}.$$ Since $(u,v)$ is light, $w(u,v)\le w(x,y)$, so $w(T')\le w(T)$ — thus $T'$ is also an MST. And $A\subseteq T'$ (we only removed a non-$A$ edge) with $(u,v)\in T'$, so $A\cup\{(u,v)\}\subseteq T'$. Therefore $(u,v)$ is safe. $\blacksquare$

This is the same exchange argument as activity selection and Huffman codes from the greedy module: take any optimal solution, swap in the greedy choice, show the result is no worse. Corollary 21.2 specializes it to the natural cut induced by a connected component of the forest $A$ — and that corollary is exactly what makes Kruskal and Prim correct. Kruskal keeps many components and merges them; Prim grows one component; both always add the lightest cross-component edge.