Trees, Spanning Trees, and Minimum Spanning Trees

⚡ Key Takeaways

A tree is a connected acyclic graph; a spanning tree of a connected graph is a subgraph that is a tree touching every vertex; a minimum spanning tree (MST) is a spanning tree of minimum total edge weight. Key result: every connected graph has a spanning tree, an $n$ -vertex tree has exactly $n-1$ edges, and MSTs can be found greedily in near-linear time (Kruskal, Prim, Borůvka). Applies to network design, clustering, circuit layout, and approximation algorithms. Foundational results from Cayley (1889), Borůvka (1926), Kruskal & Prim (1956).

💡 The Core Insight

A tree is the "just barely connected" graph: it has the minimum number of edges needed to connect all vertices, so it is simultaneously maximally acyclic and minimally connected. Adding any edge creates a cycle; removing any edge disconnects it. For minimum spanning trees, this dual rigidity powers two equivalent optimality conditions — the cut property (the lightest edge crossing any cut is safe to include) and the cycle property (the heaviest edge in any cycle can be excluded). Together they guarantee that greedy algorithms construct the optimum.

DefinitionGraph, Tree, Forest

Let $G = (V, E)$ be an undirected graph with vertex set $V$ ( $|V| = n$ ) and edge set $E$ ( $|E| = m$ ).

A path is a sequence of distinct vertices $v_0, v_1, \dots, v_k$ with each $\{v_{i}, v_{i+1}\} \in E$ .
A cycle is a path of length $\geq 3$ with $v_0 = v_k$ and otherwise distinct vertices.
$G$ is connected if there is a path between every pair of vertices.
$G$ is acyclic if it contains no cycle.
A tree is a connected acyclic graph. A forest is an acyclic graph (a disjoint union of trees).
A leaf is a vertex of degree 1.

DefinitionSpanning Tree and Minimum Spanning Tree

Let $G = (V, E)$ be a connected graph.

A spanning subgraph is a subgraph containing all vertices of $G$ .
A spanning tree $T$ of $G$ is a spanning subgraph that is a tree: $T = (V, E_T)$ with $E_T \subseteq E$ , $T$ connected and acyclic.
Given a weight function $w : E \to \mathbb{R}$ , the weight of a spanning tree is

1

\quad w(T) = \sum_{e \in E_T} w(e).

Derivation hint: the total weight is just the sum over the $n-1$ chosen edges; nothing more is hidden.

A minimum spanning tree (MST) is a spanning tree $T^*$ minimizing $w(T)$ :

2

\quad T^* = \arg\min_{T \text{ spanning tree of } G} \; w(T).

Derivation hint: the minimization ranges over the finite (but possibly exponential) set of all spanning trees.

TheoremEquivalent Characterizations of a Tree

For a graph $T$ on $n$ vertices, the following are equivalent: 1. $T$ is a tree (connected and acyclic). 2. $T$ is connected and has exactly $n-1$ edges. 3. $T$ is acyclic and has exactly $n-1$ edges. 4. Between any two vertices there is a unique path. 5. $T$ is connected, but removing any single edge disconnects it (minimally connected). 6. $T$ is acyclic, but adding any single edge creates a cycle (maximally acyclic).

TheoremEdge Count of a Tree

Every tree on $n$ vertices has exactly $n - 1$ edges:

3

\quad m = n - 1.

Derivation hint: induct on $n$ — removing a leaf removes exactly one vertex and one edge, preserving the tree property.

TheoremCayley's Formula

The number of distinct labeled spanning trees of the complete graph $K_n$ is

4

\quad \tau(K_n) = n^{\,n-2}.

Derivation hint: bijection with Prüfer sequences — strings of length $n-2$ over an $n$ -symbol alphabet.

TheoremMatrix–Tree Theorem (Kirchhoff)

For a connected graph $G$ , let $L = D - A$ be the Laplacian ( $D$ = degree diagonal matrix, $A$ = adjacency matrix). The number of spanning trees equals any cofactor of $L$ :

5

\quad \tau(G) = \det\!\big(L_{\hat{i}\hat{j}}\big),

where $L_{\hat{i}\hat{j}}$ deletes row $i$ and column $j$ . Derivation hint: Cauchy–Binet applied to the incidence matrix; each nonzero minor corresponds to a spanning tree.

ProofTree has exactly

n-1

edges

We prove statement [3] by induction on $n$ .

Step 1 (Base case). For $n = 1$ , the tree is a single vertex with $0 = 1 - 1$ edges. ✓

Step 2 (A tree has a leaf). A finite tree with $\geq 2$ vertices has at least two leaves. If every vertex had degree $\geq 2$ , we could keep walking along unused edges and, in a finite acyclic graph, eventually repeat a vertex — forming a cycle, contradicting acyclicity.

Step 3 (Inductive step). Let $T$ have $n \geq 2$ vertices. Take a leaf $v$ and remove it together with its single incident edge, giving $T'$ on $n-1$ vertices. Removing a leaf cannot create a cycle and cannot disconnect $T$ (no path used $v$ except as an endpoint), so $T'$ is a tree.

Step 4 (Apply hypothesis). By induction $T'$ has $(n-1) - 1 = n - 2$ edges. Restoring $v$ and its edge gives $T$ with $n - 1$ edges. $\blacksquare$

∎

ProofCut Property — lightest crossing edge is safe

Let $(S, V \setminus S)$ be any nontrivial cut (partition of vertices). Suppose edge $e = \{u, v\}$ with $u \in S$ , $v \notin S$ is the strictly minimum-weight edge crossing the cut. We claim every MST contains $e$ .

Step 1. Suppose for contradiction an MST $T^*$ does not contain $e$ .

Step 2. Since $T^*$ is a spanning tree, adding $e$ creates a unique cycle $C$ (Theorem characterization 6). The cycle $C$ starts in $S$ , ends in $S$ (it's a cycle through $u$ ), so it must cross the cut an even number of times; thus $C$ contains at least one other edge $f \neq e$ crossing the cut.

Step 3. Since $e$ is the strict minimum crossing edge, $w(e) < w(f)$ .

Step 4. Form $T' = T^* - f + e$ . This is connected (we removed an edge from a cycle) and has $n-1$ edges, so it is a spanning tree with $w(T') = w(T^*) - w(f) + w(e) < w(T^*)$ , contradicting minimality of $T^*$ . Hence every MST contains $e$ . $\blacksquare$

∎

ProofCycle Property — heaviest cycle edge is excludable

Let $C$ be any cycle in $G$ and let $e$ be a strictly maximum-weight edge of $C$ . Then no MST contains $e$ .

Step 1. Suppose an MST $T^*$ contains $e = \{u,v\}$ .

Step 2. Removing $e$ splits $T^*$ into two components, with $u$ and $v$ on opposite sides. The rest of cycle $C$ (the path $C - e$ ) connects $u$ to $v$ , so it must contain some edge $f$ crossing this split, $f \neq e$ .

Step 3. Since $e$ is the strict maximum on $C$ , $w(f) < w(e)$ .

Step 4. Then $T' = T^* - e + f$ is a spanning tree with $w(T') < w(T^*)$ — contradiction. $\blacksquare$

∎

TheoremUniqueness of the MST

If all edge weights are distinct, the minimum spanning tree is unique. Derivation hint: combine the cut and cycle properties — every edge is either forced in (lightest across some cut) or forced out (heaviest on some cycle), leaving no choices.

mathematician · Otakar Borůvka | 1899–1995

The Czech mathematician Otakar Borůvka published the first MST algorithm in 1926, motivated by a concrete engineering problem: the Moravian electric power company asked how to interconnect towns with the least total length of cable. His algorithm — repeatedly contracting each component's cheapest outgoing edge in parallel — predates both Kruskal's and Prim's by three decades and is enjoying a modern revival because its parallelism suits GPU and distributed computation. Borůvka also worked in differential geometry and group theory, but this early applied paper became one of the founding documents of combinatorial optimization.

🧠 Intuition

Picture the vertices as islands and candidate edges as bridges with construction costs. A spanning tree is the cheapest way to make all islands reachable without wasteful redundancy — every extra bridge beyond $n-1$ would either be useless (creating a loop) or could replace a more expensive one. The cut property is the "no regrets" rule: if you split the islands into two groups, the single cheapest bridge connecting the groups can never be wrong — you must cross that gap somehow, and that's the cheapest way to do it. The cycle property is its mirror: if your bridges ever form a loop, the most expensive bridge in the loop is redundant — you can always reach across the loop another way, so drop it. Greedy MST algorithms are just two strategies for applying these rules: Kruskal sorts all bridges cheapest-first and adds each one unless it closes a loop; Prim grows a single connected blob, always grabbing the cheapest bridge leaving the blob.

Figure

Kruskal's algorithm building an MST: edges added in increasing weight, skipping any that form a cycle

ExampleKruskal's algorithm on a 5-vertex graph

Given: Vertices $\{A,B,C,D,E\}$ with weighted edges: $AD=1,\ AB=2,\ BC=3,\ DE=4,\ BD=6,\ CE=7,\ AE=9$ .

Goal: Find the MST using Kruskal (sort edges, add cheapest-first, skip cycles).

Step 1 — Sort by weight: $AD(1), AB(2), BC(3), DE(4), BD(6), CE(7), AE(9)$ .

Step 2 — Process each edge (using a disjoint-set / union–find structure):

$AD(1)$ : components $\{A\},\{D\}$ separate → add. Sets: $\{A,D\}$ .
$AB(2)$ : $\{A,D\},\{B\}$ separate → add. Sets: $\{A,B,D\}$ .
$BC(3)$ : $\{A,B,D\},\{C\}$ separate → add. Sets: $\{A,B,C,D\}$ .
$DE(4)$ : $\{A,B,C,D\},\{E\}$ separate → add. Sets: $\{A,B,C,D,E\}$ — all connected.
$BD(6)$ : $B$ and $D$ already same set → skip (cycle).
We now have $n-1 = 4$ edges; stop.

Step 3 — Total weight: $1 + 2 + 3 + 4 = 10$ .

\boxed{\text{MST edges } = \{AD, AB, BC, DE\}, \quad w(T^*) = 10 \text{ (cost units)}}

ExamplePrim's algorithm from a start vertex

Given: Same graph as above. Run Prim starting from vertex $A$ (grow one connected blob, always take the cheapest edge leaving it).

Step 1 — Start: Tree $= \{A\}$ . Frontier edges: $AD(1), AB(2), AE(9)$ .

Step 2: Cheapest is $AD(1)$ → add $D$ . Tree $=\{A,D\}$ . Frontier: $AB(2), DE(4), BD(6), AE(9)$ .

Step 3: Cheapest is $AB(2)$ → add $B$ . Tree $=\{A,B,D\}$ . Frontier: $BC(3), DE(4), AE(9)$ (drop $BD$ , both endpoints now inside).

Step 4: Cheapest is $BC(3)$ → add $C$ . Tree $=\{A,B,C,D\}$ . Frontier: $DE(4), CE(7), AE(9)$ .

Step 5: Cheapest is $DE(4)$ → add $E$ . All vertices included.

Step 6 — Total weight: $1 + 2 + 3 + 4 = 10$ .

\boxed{\text{MST edges } = \{AD, AB, BC, DE\}, \quad w(T^*) = 10 \text{ (cost units)}}

Note both algorithms produce the same tree here — guaranteed because all weights are distinct (Uniqueness Theorem).

⚠️ Common mistake

"The MST gives the shortest path between two vertices." It does not. The MST minimizes total edge weight across the whole graph, not the distance between any particular pair. The path between two vertices in the MST can be much longer than their shortest path in the original graph. Shortest-path trees (from Dijkstra) and minimum spanning trees are different objects with different optimality criteria.

"More edges means better connectivity, so add a few extra." A spanning tree has exactly $n-1$ edges. Any additional edge creates a cycle and increases cost without improving connectivity — the tree is already connected.

"With repeated weights the MST is still unique." Only distinct weights guarantee uniqueness. With ties there can be several MSTs of equal minimum weight.

CounterexampleMST ≠ shortest-path tree

Take a triangle $A, B, C$ with weights $AB = 1$ , $BC = 1$ , $AC = 1.9$ .

MST: edges $AB$ and $BC$ , total weight $2$ . The MST path from $A$ to $C$ goes $A \to B \to C$ with length $1 + 1 = 2$ .
Shortest path $A$ to $C$ in the original graph: the direct edge $AC = 1.9 < 2$ .

So the unique path within the MST ( $=2$ ) is longer than the true shortest path ( $=1.9$ ). The MST is globally cheapest to build but does not preserve pairwise shortest distances.

connection

Trees and MSTs sit at the crossroads of several areas:

Graph Connectivity — a spanning tree is the minimal certificate that a graph is connected; the number of edges to delete to disconnect relates to cuts used in the cut property.
Greedy Algorithms — MSTs are the canonical case where greedy is optimal, formalized by the theory of Matroids: the forests of a graph form a graphic matroid, and the greedy algorithm is optimal precisely because the independent sets form a matroid.
Shortest Path Problem — Prim's algorithm is structurally almost identical to Dijkstra's, differing only in the key used (edge weight vs. accumulated distance).
Linear Algebra — the Matrix–Tree Theorem [5] counts spanning trees via the Laplacian determinant, linking combinatorics to spectral graph theory.
Network Flows and Minimum Cut — the cut property is a combinatorial cousin of max-flow/min-cut duality.

🔬 Where this appears

⏳ History

- 1847 — Gustav Kirchhoff introduces spanning trees while analyzing electrical circuits, proving the Matrix–Tree Theorem [5] for counting them.

- 1857 — Arthur Cayley uses "tree" terminology in studies of chemical isomers and combinatorial enumeration.

- 1889 — Cayley publishes the formula

\tau(K_n) = n^{n-2}

[4] for the number of labeled trees.

- 1918 — Heinz Prüfer gives an elegant bijective proof of Cayley's formula via Prüfer sequences.

- 1926 — Otakar Borůvka publishes the first MST algorithm, solving the Moravian power-network problem.

- 1930 — Vojtěch Jarník independently devises the algorithm later rediscovered as Prim's.

- 1956 — Joseph Kruskal publishes his cheapest-edge-first greedy algorithm in a now-famous short paper.

- 1957 — Robert Prim publishes the grow-one-tree algorithm (independently of Jarník), naming it after himself.

- 1975–1995 — Andrew Yao, Michael Fredman, Robert Tarjan and others push MST complexity toward linear time; in 1995 Karger, Klein, and Tarjan give an expected-linear-time randomized algorithm, and the exact deterministic optimal-comparison complexity remains studied today.

open-problem

The exact deterministic complexity of computing an MST in the comparison model is not fully resolved. We have:

A randomized algorithm (Karger–Klein–Tarjan, 1995) running in expected $O(m)$ time.
A deterministic algorithm (Chazelle, 2000) running in $O(m\,\alpha(m,n))$ time, where $\alpha$ is the inverse-Ackermann function — almost but not provably linear.
Bernard Chazelle and Seth Pettie's optimal deterministic algorithm runs in provably optimal time, but its exact asymptotic complexity is unknown — it equals the (unknown) decision-tree complexity of the MST problem.

So a genuinely open question persists: Is there a deterministic linear-time, comparison-based MST algorithm? Related open directions include MST maintenance under dynamic edge insertions/deletions and parallel/distributed MST lower bounds in the CONGEST model.

Trees, Spanning Trees, and Minimum Spanning Trees

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also