The Minimum Spanning Tree Problem

A minimum spanning tree (MST) of a connected, undirected, weighted graph is a tree connecting all vertices with the smallest possible total edge weight. MSTs underpin network design, clustering, and approximation algorithms.

Definitions

Given a connected undirected graph $G = (V, E)$ with weight function $w: E \to \mathbb{R}$, a spanning tree is an acyclic subset $T \subseteq E$ that connects all vertices ($|T| = |V| - 1$). A minimum spanning tree minimises:

$w(T) = \sum_{(u, v) \in T} w(u, v)$

MSTs need not be unique when edge weights tie.

The Cut Property

For any cut $(S, V \setminus S)$ (a partition of $V$), a light edge crossing the cut is one whose weight is minimum among all crossing edges. Light edges are not necessarily unique.

Cut Property: For any cut, every light edge crossing the cut belongs to some MST.

Proof

Let $e = (u, v)$ be a light edge crossing cut $(S, V \setminus S)$. Suppose $e$ is not in some MST $T$. Since $T$ is spanning and connected, adding $e$ to $T$ creates a unique cycle. This cycle must cross the cut at least twice: once with $e$, and at least once with another edge $f$ crossing the cut. Since $e$ is a light edge, $w(e) \le w(f)$. Remove $f$ from $T \cup \{e\}$; the resulting tree $T' = T \cup \{e\} \setminus \{f\}$ has weight $w(T') = w(T) - w(f) + w(e) \le w(T)$. Since $T$ was minimum, $T'$ is also minimum, and it contains $e$. So $e$ belongs to some MST.

The Cycle Property

Cycle Property: For any cycle in $G$, the maximum-weight edge in the cycle cannot belong to any MST.

Proof

Let $e$ be the unique maximum-weight edge on some cycle $C$. Suppose $e$ is in some MST $T$. Removing $e$ partitions $T$ into two components. Since $C$ connects these components via some other edge $f \neq e$, adding $f$ and removing $e$ yields a spanning tree $T'$ with $w(T') = w(T) - w(e) + w(f) < w(T)$, contradiction.

Generic MST Algorithm

Both Kruskal’s and Prim’s algorithms are instances of a generic strategy:

GENERIC-MST(G, w):
    A = empty set
    while A does not form a spanning tree:
        find a safe edge (u, v) for A
        A = A union {(u, v)}
    return A

An edge is safe for $A$ if $A \cup \{e\}$ is a subset of some MST. The cut property provides a way to find safe edges: any light edge crossing a cut that respects $A$ (no edges of $A$ cross the cut) is safe for $A$.

Proof of Safe-Edge Theorem

Let $A$ be a subset of some MST $T$, and let $(S, V \setminus S)$ be any cut respecting $A$. Let $e = (u, v)$ be a light edge crossing the cut. If $e \in T$, done. Otherwise, $T \cup \{e\}$ contains a cycle. This cycle must cross the cut (since $e$ does), so there is another edge $f$ on the cycle crossing the cut. $f \notin A$ (since the cut respects $A$). Remove $f$; the new tree $T' = T \cup \{e\} \setminus \{f\}$ is an MST with $A \cup \{e\} \subseteq T'$, so $e$ is safe.

Example

Graph with 6 vertices and edges: $(1,2,3)$, $(1,3,1)$, $(2,3,2)$, $(2,4,4)$, $(3,4,5)$, $(3,5,2)$, $(4,5,1)$, $(4,6,3)$, $(5,6,2)$. Weights in third position.

The MST has total weight $1 + 2 + 1 + 2 + 2 = 8$ using edges: $(1,3)$, $(2,3)$, $(4,5)$, $(5,6)$, $(3,5)$.

Summary

Concept	Definition
Spanning tree	Acyclic subgraph connecting all vertices
MST	Spanning tree with minimum total weight
Cut property	Light edge crossing any cut is in some MST
Cycle property	Maximum-weight edge on a cycle is in no MST
Safe edge	Adding it to $A$ keeps $A$ subset of some MST
Respecting cut	No edges of $A$ cross the cut

Past Tripos: y2024p2q7, y2023p1q9.