III · Graph theory
Spanning trees
What it is
Connect all vertices with V−1 edges and minimum total weight. Kruskal (sort edges + union-find) or Prim (grow from a vertex).
Where it lives
Network broadcast (one shortest path to each node), clustering, redundancy planning.
The key insight
A graph with V vertices has V^(V−2) labelled spanning trees (Cayley's formula). Unique only for unique edge weights.