Minimum spanning trees & the cut property

◈ 3 cards

Why an MST has exactly |V|−1 edges, and the one theorem (the cut property / safe edge) that justifies both Kruskal and Prim.

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 = \emptyset$ 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) \in / A$ . Form $T^{'} = T - {(x, y)} \cup {(u, v)} .$ Since $(u, v)$ is light, $w (u, v) \leq w (x, y)$ , so $w (T^{'}) \leq 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. $■$

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.

The cut property on vertices 0, 1, 2, 6, 7, 8 of the exercise graph. A = {0–1, 0–7, 6–7} lies entirely inside S = {0, 1, 6, 7}, so the cut respects A. Three edges cross it — 6–8 (6), 7–8 (7) and 1–2 (8) — and the lightest of those, 6–8, is safe to add. Edge 2–8 is lighter still (2) but does not cross this cut, so the theorem says nothing about it here.

Why "respects A" is a premise and not decoration. The cut S = {0, 1, 2, 8} against {6, 7} is crossed by 0–7, which is already in A. The exchange argument could now swap out an edge of A itself, so Theorem 21.1 guarantees nothing about the lightest edge crossing this cut.