Minimum Spanning
Trees

What is a spanning tree?

Given a connected, undirected graph G = (V, E), a spanning tree T = (V, E') is a subgraph that:

• Contains all vertices in V
• Is connected
• Is acyclic (a tree)
• Has exactly |V| - 1 edges

Minimum spanning tree

An MST is a spanning tree whose total edge weight is minimised among all spanning trees of G.

Definition

A cut partitions vertices into two non-empty sets (S, V \ S). A crossing edge has one endpoint in each set. A light edge is a crossing edge of minimum weight.

Cut property theorem

For any cut (S, V \ S), the minimum-weight crossing edge belongs to some MST.

Proof sketch

Assume the light edge e = (u, v) is not in MST T.

• Adding e to T creates a cycle
• This cycle must contain another crossing edge e'
• Since w(e) ≤ w(e'), swapping e' for e yields T' with w(T') ≤ w(T)
• Therefore T' is also an MST containing e

Definition

For any cycle C in graph G, the maximum-weight edge on C does not belong to any MST (assuming distinct weights).

Proof sketch

Assume the heaviest edge e on cycle C is in MST T. Removing e splits T into two components. The cycle C must contain another edge e' crossing this cut. Since w(e') < w(e), replacing e with e' gives a lighter spanning tree — contradiction.

Red rule / Blue rule

The abstract framework

All MST algorithms follow this pattern:

A = {}                              // MST edges
while A does not form a spanning tree:
    find a cut (S, V\S) that respects A
    add the light edge crossing (S, V\S) to A
return A

A cut respects a set A of edges if no edge in A crosses the cut.

Key insight

At every step, the algorithm maintains the invariant that A is a subset of some MST. The cut property guarantees the light edge is safe to add.

Three instantiations

Algorithm

1. Sort all edges by weight
2. For each edge (u, v) in sorted order: if u and v are in different components, add edge to MST; otherwise skip
3. Stop when |V| - 1 edges are added

KRUSKAL(G):
    sort edges by weight
    T = {}
    for each (u, v, w) in sorted edges:
        if FIND(u) != FIND(v):
            T = T ∪ {(u,v)}
            UNION(u, v)
    return T

Complexity

Operations

Optimisations

• Union by rank — attach the shorter tree under the taller tree's root
• Path compression — during FIND, make every visited node point directly to the root

FIND(x):
    if x != parent[x]:
        parent[x] = FIND(parent[x])  // path compression
    return parent[x]

UNION(x, y):
    rx, ry = FIND(x), FIND(y)
    if rank[rx] < rank[ry]: swap(rx, ry)
    parent[ry] = rx               // union by rank
    if rank[rx] == rank[ry]: rank[rx]++

Graph

Execution trace

Algorithm

1. Start from any vertex s; initialise priority queue with all vertices (key = ∞)
2. Set key[s] = 0
3. While the priority queue is not empty: extract vertex u with minimum key; for each neighbour v of u, if v is in the queue and w(u,v) < key[v], update key[v] and parent[v]

PRIM(G, s):
    for each v in V:
        key[v] = ∞, parent[v] = NIL
    key[s] = 0
    Q = min-priority-queue(V, key)
    while Q is not empty:
        u = EXTRACT-MIN(Q)
        for each (u, v, w) in adj[u]:
            if v ∈ Q and w < key[v]:
                parent[v] = u
                DECREASE-KEY(Q, v, w)
    return {(v, parent[v]) : v ∈ V \ {s}}

Algorithm (1926 — oldest MST algorithm)

1. Start with each vertex as its own component
2. In each phase, for every component: find the lightest edge leaving the component
3. Add all such edges (handle ties consistently to avoid cycles)
4. Repeat until only one component remains

Complexity analysis

• Each phase at least halves the number of components
• Therefore at most O(log V) phases
• Each phase scans all edges: O(E)
• Total: O(E log V)

Advantages

When is the MST unique?

Practical implication

When edge weights come from real-world measurements (floating point), ties are essentially impossible — the MST is almost always unique.

Proof of uniqueness with distinct weights

Suppose two distinct MSTs T₁ and T₂ exist. Let e be the lightest edge in T₁ that is not in T₂.

• Adding e to T₂ creates a cycle
• Every other edge in this cycle is in T₂ and has a different weight from e
• At least one edge e' in this cycle is not in T₁
• Since all weights are distinct and e is the lightest differing edge, w(e) < w(e')
• Replacing e' with e in T₂ gives a lighter tree — contradicting T₂ being an MST

Definition

A bottleneck spanning tree minimises the maximum edge weight across all spanning trees. The bottleneck value is the weight of the heaviest edge in the tree.

Key theorem

Every minimum spanning tree is a bottleneck spanning tree (but not necessarily vice versa).

Application

Proof

Let T_MST be an MST and T_B be a bottleneck spanning tree. Suppose the bottleneck of T_MST is edge e with weight w(e), and the bottleneck of T_B is w_B < w(e).

• Removing e from T_MST splits V into (S, V\S)
• Any spanning tree must cross this cut, so T_B has a crossing edge e' with w(e') ≤ w_B < w(e)
• Replacing e with e' in T_MST yields a lighter spanning tree
• This contradicts T_MST being an MST

The problem

Given a graph G = (V, E) and a subset S ⊆ V of terminal vertices, find the minimum-weight tree connecting all terminals. Non-terminal vertices (Steiner points) may be included.

MST vs Steiner tree

The MST heuristic (2-approximation)

1. Compute shortest paths between all pairs of terminals
2. Build a complete graph on S with shortest-path distances as weights
3. Find the MST of this complete graph
4. Map edges back to paths in G; remove redundant edges

Definitions

Algorithm selection

Theoretical frontier

The setting

Each node in a network knows only its own edges and their weights. Nodes communicate by passing messages along edges. Goal: compute the MST cooperatively.

Gallager-Humblet-Spira (1983)

A distributed version of Borůvka's algorithm:

1. Each node starts as its own fragment (component)
2. Each fragment finds its minimum-weight outgoing edge (MWOE)
3. Fragments merge along their MWOEs
4. Repeat until one fragment spans the network

Complexity

Level-based merging

Fragments have levels. Two fragments at the same level merge and increase level by 1. A lower-level fragment is absorbed into a higher-level one without level increase. This prevents O(V) phases.

Telecommunications

Connect cities with minimum total cable length. The MST gives the cheapest connected network. Variants include degree-constrained MST and capacitated MST.

Computer networks

• Spanning Tree Protocol (STP) — Ethernet switches compute a spanning tree to prevent broadcast loops
• Overlay networks — multicast trees for content distribution built as MSTs over latency graphs

Transportation

Road networks, pipeline routing, power grid design — MST provides a baseline minimum-cost connected layout before adding redundancy.

Approximation backbone

MST is used as a subroutine in approximation algorithms for harder problems:

Single-linkage clustering

1. Build the MST of the data points (using pairwise distances as edge weights)
2. Remove the k - 1 heaviest edges
3. The resulting k connected components are the clusters

This is equivalent to single-linkage hierarchical clustering and produces a dendrogram naturally from the MST.

Image segmentation

Felzenszwalb & Huttenlocher (2004):

1. Build a graph where pixels are vertices and edges connect adjacent pixels with weight = colour difference
2. Run a modified Kruskal's: merge components if the edge weight is below an adaptive threshold
3. Result: over-segmented regions that respect strong boundaries

Other applications