Spanning Trees and Minimum Spanning Trees

Spanning trees provide a minimal connected subgraph that reaches all vertices, making them fundamental for network design, broadcasting protocols, and optimization problems in weighted graphs.

DefinitionSpanning Tree

A spanning tree of a connected graph $G = (V, E)$ is a subgraph $T = (V, E')$ that is a tree. Thus $T$ includes all vertices of $G$ and $|E'| = |V| - 1$ edges that maintain connectivity without cycles.

Every connected graph has at least one spanning tree. A graph with $n$ vertices and $m$ edges can have spanning trees if and only if $m \geq n - 1$ and the graph is connected.

TheoremNumber of Spanning Trees

For a complete graph $K_n$ , Cayley's formula gives the number of distinct spanning trees: $\tau(K_n) = n^{n-2}$

For example, $K_4$ has $4^2 = 16$ spanning trees. This formula shows the exponential growth in network design options.

DefinitionMinimum Spanning Tree (MST)

Given a weighted graph $G = (V, E, w)$ where $w: E \to \mathbb{R}$ assigns weights to edges, a minimum spanning tree is a spanning tree $T$ that minimizes the total weight: $w(T) = \sum_{e \in T} w(e)$

MSTs are not necessarily unique, but all MSTs of $G$ have the same total weight.

ExampleNetwork Design

Consider connecting 5 cities with roads where edge weights represent construction costs. The complete graph $K_5$ has $\binom{5}{2} = 10$ possible roads. An MST selects exactly 4 roads that connect all cities with minimum total cost. If weights are $(1,2,3,4,5,6,7,8,9,10)$ for edges in increasing order, Kruskal's algorithm would select edges with weights $1,2,3,4$ (if they don't form cycles), giving total cost 10.

DefinitionCut Property

A cut $(S, V \setminus S)$ partitions vertices into two sets. A crossing edge has one endpoint in $S$ and one in $V \setminus S$ .

Cut Property: For any cut with no MST edges crossing it, the minimum-weight crossing edge must be in some MST. This property underlies both Prim's and Kruskal's algorithms.

Remark

Prim's Algorithm grows an MST from a single vertex by repeatedly adding the minimum-weight edge connecting the tree to a new vertex. Kruskal's Algorithm sorts all edges by weight and adds edges that don't create cycles, using a union-find data structure. Both run in $O(m \log n)$ time with appropriate data structures.

DefinitionCycle Property

Cycle Property: For any cycle $C$ in $G$ , the maximum-weight edge in $C$ is not in any MST (unless multiple edges tie for maximum weight).

This provides a complementary perspective to the cut property and enables alternative MST algorithms and proofs of correctness.

Spanning trees and MSTs are central to network optimization, circuit design, approximation algorithms, and serve as building blocks for more complex graph algorithms like traveling salesman problem approximations.