Chapter 32 — Key Takeaways

Spanning trees, minimum spanning trees, and network design — the re-grounding card. Reread before an exam.

Core definitions

Two structural identities (the engine of every proof here):

• Add any non-tree edge to a spanning tree $\Rightarrow$ creates exactly one cycle.
• Remove any edge from a spanning tree $\Rightarrow$ splits it into exactly two components.

Counting facts (cited, not proved): Cayley's formula — $K_n$ has $n^{n-2}$ spanning trees. General count — any cofactor of the Laplacian (Kirchhoff's matrix-tree theorem).

The two algorithms

Kruskal skeleton: sort edges ascending → for each, if endpoints in different components, add + union → stop at $n-1$ edges.

Prim skeleton: start = one vertex → repeatedly add min-weight edge crossing tree boundary → stop when all vertices in.

Correctness: two theorems

Proof technique for both: the exchange argument —

Assume an optimal solution that disagrees with the greedy choice; swap the greedy edge in and a worse edge out; show the swap does not increase (cut property) or strictly decreases (cycle property) weight; conclude.

Corollary: distinct edge weights $\Rightarrow$ unique MST (Kruskal and Prim return the same tree).

Decision aid — "which tool do I reach for?"

Common pitfalls

• ❌ "The MST gives the shortest path between every pair." No — MST minimizes total weight, not per-pair distance. (Triangle $XY{=}1, YZ{=}1, XZ{=}1.5$: MST path $X\to Z$ costs $2$, but the direct edge is $1.5$.)
• ❌ Forgetting the cycle test in Kruskal. Without find(u) != find(v), you build cycles, not a tree.
• ❌ Sorting descending for Kruskal. Kruskal is ascending; descending-with-keep-connected is the reverse-delete algorithm.
• ❌ Confusing MST with min-max objectives. MST minimizes the sum; if you need to minimize the single most expensive link or the longest path, that's a different problem. (Bonus: MST does minimize the max edge on the path between any two vertices — the minimax property.)
• ❌ Assuming the MST is unique. Only guaranteed when all weights are distinct; ties allow multiple MSTs.
• ❌ Treating a tree as fault-tolerant. Any single edge removal disconnects a tree.

Toolkit additions (dmtoolkit/graphs.py)

def mst_kruskal(g):
    uf = UnionFind(g.vertices())
    mst, total = [], 0
    for u, v, w in sorted(g.edges(), key=lambda e: e[2]):
        if uf.union(u, v):
            mst.append((u, v, w)); total += w
    return mst, total

Builds toward the capstone (Ch. 39 Track B: social-network analyzer extracts a cheapest backbone). Ch. 34 adds max_flow to finish graphs.py.

One-line summary

A spanning tree is the minimal scaffolding ($n-1$ edges) that keeps a graph connected; the MST is the cheapest one; two greedy algorithms (Kruskal via union-find, Prim via a heap) find it in $O(E\log V)$; both are provably optimal because of the cut property, itself proved by an exchange argument.