Minimum Spanning Tree

Minimum spanning tree (MST, or minimum-weight spanning tree) is a fundamental combinatorial structure in graph theory and computation and algorithms: given a connected, undirected graph G = (V, E) with a real-valued edge-weight function w : E → ℝ, a minimum spanning tree is a subset of edges T ⊆ E that connects all |V| vertices without forming cycles and minimizes total edge weight w(T) = ∑_{e ∈ T} w(e). When G is disconnected, a minimum spanning tree within each connected component forms a minimum spanning forest.

First formulated in 1926 by Czech mathematician Otakar Borůvka to design an economical electrical distribution grid across Moravia, the minimum spanning tree problem serves as the canonical model for greedy algorithm design and graphic matroid optimization within computational complexity theory. Beyond power grids and VLSI circuit routing, minimum spanning trees underpin single-linkage hierarchical clustering, minimum spanning haplotype network inference in molecular epidemiology, metric Traveling Salesperson approximations, and spectral graph Laplacian preconditioners.

Structural Properties of Spanning Trees

Let G = (V, E) be a connected undirected graph with n = |V| vertices and m = |E| edges. Every spanning tree T = (V, E_T) of G is connected, acyclic, and contains |E_T| = |V| − 1 edges, with a unique simple path in T between any two vertices u, v ∈ V. Adding any non-tree edge e ∈ E \ E_T to T creates a unique fundamental cycle C(e), and removing any single edge f ∈ C(e) from T ∪ {e} yields another spanning tree. Conversely, removing any tree edge f ∈ E_T partitions V into two disconnected sets (S, V \ S), defining a fundamental cut.

By Cayley's formula (1889), a complete graph K_n contains nⁿ⁻² spanning trees (and by Kirchhoff's Matrix-Tree Theorem, the number of spanning trees of G equals any cofactor of its graph Laplacian matrix L = D − A). Despite this large search space, the global minimum-weight spanning tree is constructed greedily without backtracking via two dual principles formalized by Robert Tarjan (1983) as the blue rule (cut property) and red rule (cycle property).

The Cut Property (Blue Rule) and Cycle Property (Red Rule)

• Cut Property (Safe-Edge Inclusion): A cut (S, V \ S) partitions V into two non-empty disjoint subsets. If A ⊆ E is a subset of edges contained in some MST of G and no edge in A crosses (S, V \ S), then any minimum-weight edge e^* crossing (S, V \ S) is safe for A—meaning A ∪ {e^*} is also a subset of some MST.

Proof (Exchange Argument): Let T be an MST containing A. If e^* ∉ T, adding e^* to T creates a cycle C that must cross back across (S, V \ S) via another edge f ∈ T \ A with w(e^*) ≤ w(f). Swapping f for e^* yields a spanning tree T′ = (T \ {f}) ∪ {e^*} of weight w(T′) = w(T) − w(f) + w(e^*) ≤ w(T).

• Cycle Property (Heavy-Edge Exclusion): For any simple cycle C in G, if an edge e_max ∈ C has weight greater than every other edge in C, then e_max cannot belong to any MST of G.
• Uniqueness and Bottleneck Optimality: If all edge weights in G are pairwise distinct, every cut has a unique lightest edge and the MST of G is unique. Every MST is also a minimum bottleneck spanning tree, minimizing the maximum edge weight along the unique tree path between every pair of vertices.

Borůvka's Parallel Contraction (1926) and Kruskal's Disjoint-Set Algorithm (1956)

In each phase of Borůvka's algorithm, every current connected component C_i simultaneously selects its lightest outgoing edge e_i^*. Merging components across all selected edges in O(|E|) time halves the number of connected components in each phase, terminating in at most ⌈log₂ |V|⌉ phases and O(|E| log |V|) time with high parallel efficiency.

Formulated by Joseph B. Kruskal in 1956, Kruskal's algorithm sorts all edges in non-decreasing weight order (w(e₁) ≤ ··· ≤ w(e_m)) in O(|E| log |E|) = O(|E| log |V|) time and scans them sequentially, adding edge (u, v) if and only if u and v lie in different components. Component tracking via Robert Tarjan's disjoint-set union (Union-Find) structure with union by rank and path compression executes all O(|E|) Find and Union operations in O(|E| α(|V|)) nearly linear time, where α(n) ≤ 4 is the inverse Ackermann function.

Jarník–Prim Frontier Growth (1930 / 1957) and Linear Randomized Bounds

Independently discovered by Vojtěch Jarník (1930), Robert C. Prim (1957), and Edsger W. Dijkstra (1959), Prim's algorithm grows a single tree T from an arbitrary root r, maintaining for each non-tree vertex v the minimum edge weight *key*[v] connecting v to T. Using a binary heap yields O(|E| log |V|) time, whereas Michael Fredman and Robert Tarjan's Fibonacci heap (1987) performs |V| Extract-Min operations in O(|V| log |V|) amortized time and |E| Decrease-Key operations in O(|E|) amortized time, achieving O(|E| + |V| log |V|) total time.

In 1995, David Karger, Philip Klein, and Robert Tarjan interleaved Borůvka steps with random subgraph sampling to achieve O(|E|) expected linear time, and in 2000 Bernard Chazelle used approximate soft heaps to achieve a deterministic O(|E| α(|E|, |V|)) bound.

Single-Linkage Clustering and Minimum Spanning Haplotype Networks

In multivariate statistics and bioinformatics, single-linkage agglomerative clustering is isomorphic to Kruskal's MST algorithm: deleting the k − 1 heaviest edges of an MST partitions a dataset into k clusters that maximize minimum inter-cluster separation. In genomic epidemiology, when intraspecific sequences exhibit low divergence and ancestral genotypes coexist with descendants, minimum spanning haplotype networks connect observed sequences by minimum mutational sequence alignment edit distances to reconstruct outbreak transmission chains.

Metric Traveling Salesperson Approximations

When edge weights satisfy the triangle inequality w(u, v) ≤ w(u, x) + w(x, v), the MST weight w(T^*) bounds the optimal Traveling Salesperson tour w(TSP^*) from below. Doubling every edge of T^* and shortcutting visited vertices during a depth-first walk yields a 2-approximation tour, while pairing the odd-degree vertices of T^* via a minimum-weight perfect matching (Christofides–Serdyukov, 1976) achieves a 3/2-approximation.

How does a minimum spanning tree differ from a shortest-path tree?

A minimum spanning tree minimizes the total sum of all tree edge weights ∑_{e ∈ T} w(e), whereas a single-source shortest-path tree minimizes the individual path distance δ(s, v) from root s to each vertex v. In a triangle {s, a, b} with weights w(s, a) = 5, w(s, b) = 5, and w(a, b) = 4, the MST uses (s, a) and (a, b) with total weight 9, whereas the shortest-path tree from s uses (s, a) and (s, b) with total weight 10.

What happens if a graph has negative edge weights when computing a minimum spanning tree?

Because every spanning tree is acyclic and contains |V| − 1 edges, Borůvka's, Kruskal's, and Prim's algorithms work without modification on negative edge weights. Adding a constant +C to every edge simply shifts the total weight of every spanning tree by (|V| − 1)C, preserving the MST.

1. Kruskal, J. B. (1956). "On the shortest spanning subtree of a graph and the traveling salesman problem." Proceedings of the American Mathematical Society, 7(1), 48–50. https://doi.org/10.1090/S0002-9939-1956-0078686-7
2. Prim, R. C. (1957). "Shortest connection networks and some generalizations." Bell System Technical Journal, 36(6), 1389–1401. https://doi.org/10.1002/j.1538-7305.1957.tb01515.x
3. Fredman, M. L., & Tarjan, R. E. (1987). "Fibonacci heaps and their uses in improved network optimization algorithms." Journal of the ACM, 34(3), 596–615. https://doi.org/10.1145/28869.28874
4. Karger, D. R., Klein, P. N., & Tarjan, R. E. (1995). "A randomized linear-time algorithm to find minimum spanning trees." Journal of the ACM, 42(2), 321–328. https://doi.org/10.1145/201019.201022
5. Chazelle, B. (2000). "A minimum spanning tree algorithm with inverse-Ackermann type complexity." Journal of the ACM, 47(6), 1028–1047. https://doi.org/10.1145/355541.355562