Trees, Spanning Trees, and Minimum Spanning Trees

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).

A tree is one of the most fundamental structures in graph theory: a connected graph with no cycles. Trees on $n$ vertices have a remarkable rigidity — they have exactly $n - 1$ edges, a unique path between any two vertices, and removing any edge disconnects them while adding any edge creates exactly one cycle. A spanning tree extracts such a minimal connected skeleton from a larger graph, and when edges carry weights (costs, distances, resistances), the minimum spanning tree is the cheapest way to keep everything connected. The surprising fact is that this global optimization problem yields entirely to local greedy decisions — picking the cheapest safe edge at each step is provably optimal, a rarity that makes MSTs a textbook example of when greed works.

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.

Formal Statement

Graph, 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.

Spanning 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 R$ , the weight of a spanning tree is

w (T) = e \in E_{T} \sum w (e) .

⟳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)$ :

T^{*} = ar g T spanning tree of G min w (T) .

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

Equivalent Characterizations of a Tree

For a graph $T$ on $n$ vertices, the following are equivalent:

$T$ is a tree (connected and acyclic).
$T$ is connected and has exactly $n - 1$ edges.
$T$ is acyclic and has exactly $n - 1$ edges.
Between any two vertices there is a unique path.
$T$ is connected, but removing any single edge disconnects it (minimally connected).
$T$ is acyclic, but adding any single edge creates a cycle (maximally acyclic).

Edge Count of a Tree

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

m = n - 1.

⟳induct on

n

— removing a leaf removes exactly one vertex and one edge, preserving the tree property.

Cayley's Formula

The number of distinct labeled spanning trees of the complete graph $K_{n}$ is

τ (K_{n}) = n^{n - 2} .

⟳bijection with Prüfer sequences — strings of length

n - 2

over an

n

-symbol alphabet.

Matrix–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$ :

τ (G) = det (L_{\hat{i} \hat{j}}),

where $L_{\hat{i} \hat{j}}$ deletes row $i$ and column $j$ .

⟳Cauchy–Binet applied to the incidence matrix; each nonzero minor corresponds to a spanning tree.

Why It Holds / Derivation

Tree 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^{'}

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.

■

Cut Property — lightest crossing edge is safe

Let $(S, V ∖ S)$ be any nontrivial cut (partition of vertices). Suppose edge $e = {u, v}$ with $u \in S$ , $v \in / 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

■

Cycle 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

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.

■

Uniqueness of the MST

If all edge weights are distinct, the minimum spanning tree is unique.

⟳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.

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.

Building 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.

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

Worked Examples

Kruskal's algorithm on a 5-vertex graph

Given: Vertices

{A, B, C, D, E}

with weighted edges:

A D = 1, A B = 2, B C = 3, D E = 4, B D = 6, C E = 7, A E = 9

. Goal: Find the MST using Kruskal (sort edges, add cheapest-first, skip cycles). Step 1 — Sort by weight:

A D (1), A B (2), B C (3), D E (4), B D (6), C E (7), A E (9)

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

$A D (1)$ : components ${A}, {D}$ separate → add. Sets: ${A, D}$ .
$A B (2)$ : ${A, D}, {B}$ separate → add. Sets: ${A, B, D}$ .
$B C (3)$ : ${A, B, D}, {C}$ separate → add. Sets: ${A, B, C, D}$ .
$D E (4)$ : ${A, B, C, D}, {E}$ separate → add. Sets: ${A, B, C, D, E}$ — all connected.
$B D (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

MST edges = {A D, A B, B C, D E}, w (T^{*}) = 10 (cost units)

Prim'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:

A D (1), A B (2), A E (9)

. Step 2: Cheapest is

A D (1)

→ add

D

. Tree

= {A, D}

. Frontier:

A B (2), D E (4), B D (6), A E (9)

. Step 3: Cheapest is

A B (2)

→ add

B

. Tree

= {A, B, D}

. Frontier:

B C (3), D E (4), A E (9)

(drop

B D

, both endpoints now inside). Step 4: Cheapest is

B C (3)

→ add

C

. Tree

= {A, B, C, D}

. Frontier:

D E (4), C E (7), A E (9)

. Step 5: Cheapest is

D E (4)

→ add

E

. All vertices included. Step 6 — Total weight:

1 + 2 + 3 + 4 = 10

MST edges = {A D, A B, B C, D E}, w (T^{*}) = 10 (cost units)

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

Common Misconceptions

"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.

MST ≠ shortest-path tree

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

MST: edges $A B$ and $B C$ , 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 $A C = 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.

Connections

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.

Real-World Applications

Telecommunication & power grid design — Borůvka's original 1926 problem: lay minimum total cable to connect all towns/substations. Still used in fiber-optic and electrical network planning.
Cluster analysis (single-linkage clustering) — building an MST then removing the $k - 1$ heaviest edges partitions data into $k$ clusters; the basis of the classic single-linkage hierarchical method and of the DBSCAN/HDBSCAN family.
Approximation for the Traveling Salesman Problem — doubling an MST and shortcutting gives a 2-approximation; Christofides' algorithm improves this to 1.5 using an MST plus a matching.
Image segmentation & computer vision — Felzenszwalb–Huttenlocher segmentation grows regions via MST-like merging of pixel-affinity graphs.
Circuit and VLSI layout — routing wires (Steiner/rectilinear MSTs) to minimize total interconnect length and capacitance.
Phylogenetics & taxonomy — minimum spanning networks approximate evolutionary trees connecting genetic sequences with minimal total mutation distance.
Network protocols — the Spanning Tree Protocol (STP, IEEE 802.1D) keeps Ethernet bridged networks loop-free by computing a spanning tree of switches.

Historical Development

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 $τ (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.

Subtleties & Limits

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 α (m, n))$ time, where $α$ 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

The Core Insight

Formal Statement

Graph, Tree, Forest

Spanning Tree and Minimum Spanning Tree

Equivalent Characterizations of a Tree

Edge Count of a Tree

Cayley's Formula

Matrix–Tree Theorem (Kirchhoff)

Why It Holds / Derivation

Tree has exactly $n-1$ edges

Cut Property — lightest crossing edge is safe

Cycle Property — heaviest cycle edge is excludable

Uniqueness of the MST

Otakar Borůvka | 1899–1995

Building Intuition

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

Worked Examples

Kruskal's algorithm on a 5-vertex graph

Prim's algorithm from a start vertex

Common Misconceptions

MST ≠ shortest-path tree

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also

Before this

Where this leads