---
title: Minimum Spanning Trees
module: Graphs
moduleNumber: 6
lessonNumber: 4
order: 604
summary: |
  Given a weighted network, how do we connect everything as cheaply as possible?
  The answer is a minimum spanning tree, and one lemma — the cut property —
  justifies _every_ correct MST algorithm. We prove the cut and cycle
  properties by exchange arguments, use them to settle uniqueness, and meet the
  oldest MST algorithm, Borůvka's, whose parallel component-merging rounds fall
  straight out of the cut rule.
topics: [Minimum Spanning Trees]
sources:
  - book: CLRS
    ref: "Ch. 23 — Minimum Spanning Trees"
  - book: Erickson
    ref: "Ch. 8 — Minimum Spanning Trees"
  - book: Skiena
    ref: "§6 — Weighted Graph Algorithms"
practice:
  - title: 'Min Cost to Connect All Points'
    slug: min-cost-to-connect-all-points
    difficulty: Medium
  - title: 'Find Critical and Pseudo-Critical Edges in MST'
    slug: find-critical-and-pseudo-critical-edges-in-minimum-spanning-tree
    difficulty: Hard
---


Suppose you must lay cable to connect a set of towns, and every possible
connection has a known cost. You want all the towns linked — any town reachable
from any other — while spending as little as possible. Laying a redundant link
would only waste money, so the cheapest solution can contain no cycle: it is a
**tree** that **spans** every town. Finding the cheapest such tree is the
**minimum spanning tree** problem, and it is the first place in this course
where a [_greedy_](/algorithms/greedy/the-greedy-method) strategy is provably
optimal.

## The problem

Stated precisely, in the shape the rest of this lesson will use:

> **Input.** A weighted, _undirected_ graph $G = (V, E)$ with a weight function
> $c : E \to \mathbb{R}$. Negative weights are allowed.
>
> **Precondition.** $G$ is connected.
>
> **Output.** A **minimum spanning tree** (MST) of $G$: a subset
> $E' \subseteq E$ such that $T = (V, E')$ is a tree and
> $\text{cost}(T) = \sum_{e \in E'} c_e$ is minimized.

Here a **tree** means a _connected, acyclic_ graph, not to be confused with a
rooted or rooted-and-ordered tree; an MST has no distinguished root. A spanning
tree on $n = |V|$ vertices always has exactly $n - 1$ edges: enough to connect
everything, one fewer than would create a cycle.

The word "tree" here admits several equivalent characterizations, any one of
which could serve as the definition.

> **Theorem (Tree characterizations).**
>
> 1. $G$ is a tree (connected and acyclic).
> 2. $G$ is connected and every edge is a **bridge** (an edge whose removal
>    increases the number of connected components).
> 3. $G$ is acyclic, and adding any edge in $\binom{V}{2} \setminus E$ creates a
>    cycle.
> 4. $G$ is connected and $|E| = |V| - 1$.
> 5. $G$ is acyclic and $|E| = |V| - 1$.

Below, a weighted graph and one of its minimum spanning trees (the thick
colored edges). This nine-town graph is the running example for the whole
lesson: every trace and every snapshot below runs on it.

$$
% caption: A weighted graph with one minimum spanning tree shown in thick edges.
\begin{tikzpicture}[
  every node/.style={circle, draw, minimum size=7mm, inner sep=0pt, font=\small},
  mst/.style={line width=1.6pt, draw=acc},
  wt/.style={font=\scriptsize, inner sep=1pt, draw=none}]
  \definecolor{acc}{HTML}{2348F2}
  \node (b) at (1.4,1.8) {$b$};
  \node (c) at (3.4,1.8) {$c$};
  \node (d) at (5.4,1.8) {$d$};
  \node (a) at (0.4,0.6) {$a$};
  \node (i) at (3.0,0.6) {$i$};
  \node (e) at (6.2,0.4) {$e$};
  \node (h) at (1.6,-0.7) {$h$};
  \node (g) at (3.4,-0.9) {$g$};
  \node (f) at (5.2,-0.7) {$f$};
  % non-tree edges
  \draw (a) -- node[wt,left]{$8$} (h);
  \draw (b) -- node[wt,above]{$11$} (i);
  \draw (d) -- node[wt,left]{$14$} (f);
  \draw (e) -- node[wt,right]{$10$} (f);
  \draw (i) -- node[wt,left]{$7$} (h);
  % tree edges (MST)
  \draw[mst] (a) -- node[wt,above left]{$4$} (b);
  \draw[mst] (b) -- node[wt,above]{$7$} (c);
  \draw[mst] (c) -- node[wt,above]{$7$} (d);
  \draw[mst] (c) -- node[wt,right]{$2$} (i);
  \draw[mst] (d) -- node[wt,above]{$9$} (e);
  \draw[mst] (i) -- node[wt,right]{$6$} (g);
  \draw[mst] (h) -- node[wt,below]{$1$} (g);
  \draw[mst] (g) -- node[wt,below]{$2$} (f);
\end{tikzpicture}
$$

The thick tree spans all nine towns with total weight
$1 + 2 + 2 + 4 + 6 + 7 + 7 + 9 = 38$; no spanning tree is cheaper.

## Safe edges and the generic method

Every algorithm in this lesson is an instance of one greedy template: maintain
a set $A$ of edges that is always a subset of _some_ MST, and at each step add
one more **safe** edge, meaning an edge that can be added to $A$ while keeping
$A \subseteq$ (some MST).[^clrs-cut]

```algorithm
caption: $\textsc{Generic-MST}(G, c)$ — the template every MST algorithm instantiates
number: 1
$A \gets \emptyset$
while $A$ is not a spanning tree do
  find an edge $e$ that is safe for $A$ // the only hard step
  $A \gets A \cup \set{e}$
return $A$
```

> **Invariant.** Before every iteration of the loop, $A$ is a subset of the
> edge set of some minimum spanning tree of $G$.

The invariant holds trivially at initialization ($\emptyset$ is a subset of any
MST), it is maintained by the definition of _safe_, and at termination it does
all the work: $A$ has $n - 1$ edges and is contained in some MST $T$, but $T$
also has exactly $n - 1$ edges, so $A = T$. The loop runs exactly $n - 1$
times, once per added edge.

Two things are not obvious. First, a safe edge always _exists_ while $A$ is
not yet spanning: the invariant gives an MST $T \supseteq A$, and any edge of
$T \setminus A$ is safe by definition. Second, and harder, a safe edge must be
_recognizable_ without already knowing an MST — otherwise the template is
circular. The entire theory of MSTs reduces to two local certificates:
the **cut property**, which certifies that an edge is safe to _include_, and
the **cycle property**, which certifies that an edge is safe to _exclude_.

## The cut property

First, the vocabulary. A **cut** $(S, V \setminus S)$ is a partition of the
vertices into two groups. An edge **crosses** the cut if its endpoints lie on
opposite sides. A cut **respects** an edge set $A$ if no edge of $A$ crosses it.
An edge crossing the cut is **light** (or _cheapest_) if it has the minimum
weight of all crossing edges.

$$
% caption: A cut splitting vertices into $S$ and its complement $V \setminus S$, with the
%          light crossing edge $(u, v)$ highlighted.
\begin{tikzpicture}[
  v/.style={circle, fill=black, inner sep=1.6pt},
  cross/.style={line width=1.4pt, draw=acc}]
  \definecolor{acc}{HTML}{2348F2}
  % left blob S
  \draw[draw=black] (-0.2,-1.1) rectangle (3.0,1.3);
  \node at (1.4,-1.45) {$S$};
  \node[v] (u) at (2.6,0.2) {};
  \node[below=1pt of u, font=\scriptsize] {$u$};
  \node[v] (s1) at (0.4,0.7) {};
  \node[v] (s2) at (1.0,-0.4) {};
  \node[v] (s3) at (1.7,0.6) {};
  \draw (s1)--(s3); \draw (s2)--(s3); \draw (s3)--(u);
  % right blob V minus S
  \draw[draw=black] (4.0,-1.1) rectangle (7.2,1.3);
  \node at (5.6,-1.45) {$V$ - $S$};
  \node[v] (vv) at (4.4,0.2) {};
  \node[above=1pt of vv, font=\scriptsize] {$v$};
  \node[v] (t1) at (6.0,0.7) {};
  \node[v] (t2) at (6.8,-0.3) {};
  \node[v] (t3) at (5.5,-0.5) {};
  \draw (vv)--(t3); \draw (t3)--(t2); \draw (t1)--(t2);
  % crossing light edge
  \draw[cross] (u) -- node[midway, above, font=\footnotesize, draw=none]{\texttt{light}}
    node[midway, below, font=\scriptsize, draw=none]{$c_{uv}$ min} (vv);
\end{tikzpicture}
$$

> **Theorem (Cut property).** Let $A$ be a subset of some MST of $G$. Let
> $(S, V \setminus S)$ be any cut that respects $A$, and let $e = (u, v)$ with
> $u \in S$, $v \in V \setminus S$ be a light edge crossing that cut. Then $e$ is
> safe for $A$: there is an MST containing $A \cup \set{e}$.

> **Proof (an exchange argument — done carefully).** Let $T^\ast$ be an MST
> containing $A$, and suppose, for contradiction, that _no_ MST contains $e$. Since
> $T^\ast$ is connected, there is at least one edge of $T^\ast$ crossing the cut
> $(S, V \setminus S)$.
>
> It is tempting to grab _any_ such crossing edge $f \in T^\ast$, swap it for $e$, and
> argue $T^\ast - f + e$ is a cheaper tree. **This is a mistake**: removing an
> arbitrary crossing edge $f$ need not reconnect into a tree once we add $e$; the
> result can be disconnected or contain a cycle. We must remove the _right_ edge.
>
> So instead: adding $e$ to $T^\ast$ creates a unique cycle, and because $e$ crosses
> the cut, that cycle must cross back at some edge $g \in T^\ast$, with $g$ also
> crossing $(S, V \setminus S)$. Because the cut **respects** $A$, this $g \notin A$.
> Form
> $$
> T' = T^\ast - \set{g} + \set{e}.
> $$
> Deleting $g$ breaks the unique cycle, so $T'$ is again a spanning tree, and it
> still contains $A \cup \set{e}$. Since $e$ is the _light_ crossing edge,
> $c_e \le c_g$, hence
> $$
> \text{cost}(T') = \text{cost}(T^\ast) - c_g + c_e \le \text{cost}(T^\ast).
> $$
> But $T^\ast$ was minimum, so equality holds: $T'$ is _also_ an MST, and it contains
> $e$. Contradiction. Therefore some MST contains $A \cup \set{e}$, i.e. $e$ is
> safe. $\qed$

$$
% caption: The exchange inside $T^*$: adding $e$ creates one cycle; that cycle re-crosses
%          the cut at some tree edge $g \notin A$, and $T^* - g + e$ is again a spanning
%          tree, no heavier than $T^*$.
\begin{tikzpicture}[
  v/.style={circle, fill=black, inner sep=1.6pt},
  emph/.style={line width=1.5pt},
  swap/.style={line width=1.5pt, dashed}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{D1342B}
  \draw[dashed, black] (3.1,-1.4) -- (3.1,1.6);
  \node[font=\scriptsize, black] at (0.6,1.4) {$S$};
  \node[font=\scriptsize, black] at (6.0,1.4) {$V$ - $S$};
  \node[v] (u) at (1.8,0.7) {}; \node[above=1pt of u, font=\scriptsize]{$u$};
  \node[v] (v) at (4.4,0.7) {}; \node[above=1pt of v, font=\scriptsize]{$v$};
  \node[v] (x) at (1.2,-0.6) {};
  \node[v] (y) at (4.9,-0.6) {};
  \node[v] (p) at (5.9,0.3) {};
  % cycle: e (u-v) plus tree path back through g
  \draw[emph, draw=acc] (u) -- node[above, font=\scriptsize, draw=none, fill=white, inner sep=1.5pt]{$e$} (v);
  \draw (u) -- (x);
  \draw[swap, draw=red] (x) -- node[below, font=\scriptsize, draw=none]{$g$} (y);
  \draw (y) -- (v);
  \draw (v) -- (p);
\end{tikzpicture}
$$

Here is the same picture on the nine-town graph.
Take $S = \set{a, b, c, d, e}$, the towns above the dashed line. Five edges
cross this cut: $a$–$h$ at $8$, $b$–$i$ at $11$, $c$–$i$ at $2$, $d$–$f$ at
$14$, and $e$–$f$ at $10$. The light one is $c$–$i$, so the cut property
guarantees that $c$–$i$ belongs to some MST — and indeed it is in the thick tree
above. Both Kruskal and Prim will commit to $c$–$i$ early, each by building a
cut like this one.

$$
% caption: A concrete cut on the nine-town graph: $S = \set{a,b,c,d,e}$ above the dashed
%          line. Five edges cross; the light one, $c$–$i$ at weight $2$, is safe.
\begin{tikzpicture}[
  every node/.style={circle, draw, minimum size=7mm, inner sep=0pt, font=\small},
  wt/.style={font=\scriptsize, inner sep=1pt, draw=none},
  light/.style={line width=1.6pt, draw=acc}]
  \definecolor{acc}{HTML}{2348F2}
  \node (b) at (1.4,1.8) {$b$};
  \node (c) at (3.4,1.8) {$c$};
  \node (d) at (5.4,1.8) {$d$};
  \node (a) at (0.4,0.6) {$a$};
  \node (i) at (3.0,0.6) {$i$};
  \node (e) at (6.2,0.4) {$e$};
  \node (h) at (1.6,-0.7) {$h$};
  \node (g) at (3.4,-0.9) {$g$};
  \node (f) at (5.2,-0.7) {$f$};
  % edges inside a side (muted)
  \draw[black] (a) -- node[wt,above left]{$4$} (b);
  \draw[black] (b) -- node[wt,above]{$7$} (c);
  \draw[black] (c) -- node[wt,above]{$7$} (d);
  \draw[black] (d) -- node[wt,above]{$9$} (e);
  \draw[black] (i) -- node[wt,pos=0.4,above]{$7$} (h);
  \draw[black] (i) -- node[wt,right]{$6$} (g);
  \draw[black] (h) -- node[wt,below]{$1$} (g);
  \draw[black] (g) -- node[wt,below]{$2$} (f);
  % crossing edges
  \draw (a) -- node[wt,pos=0.7,left]{$8$} (h);
  \draw (b) -- node[wt,above]{$11$} (i);
  \draw (d) -- node[wt,pos=0.65,left]{$14$} (f);
  \draw (e) -- node[wt,pos=0.78,right]{$10$} (f);
  \draw[light] (c) -- node[wt,pos=0.75,right]{$2$} (i);
  % the cut
  \draw[dashed, black, line width=1pt] plot[smooth, tension=0.8] coordinates
    {(-0.8,0.0) (1.6,0.15) (3.1,1.25) (4.4,1.05) (5.4,0.55) (6.2,-0.2) (7.1,-0.4)};
  \node[wt, black] at (-0.5,0.45) {cut};
  \node[wt] at (6.9,1.3) {$S$};
  \node[wt] at (7.0,-1.0) {$V$ - $S$};
\end{tikzpicture}
$$

Every correct MST algorithm — Borůvka's,
Prim's, or Kruskal's — is a strategy for _choosing which cut to apply the
property to_, and **all three only ever add edges that obey the cut rule.**

## The cycle property

The cut property justifies including edges; its mirror image justifies
_discarding_ them.[^erickson-mst]

> **Theorem (Cycle property).** Let $C$ be any cycle in $G$ and let $f$ be a
> maximum-weight edge on $C$. Then some MST omits $f$. If $f$ is the _unique_
> heaviest edge on $C$, then **no** MST contains $f$.

> **Proof (exchange again).** Suppose a spanning tree $T$ contains
> $f = (u, v)$. Deleting $f$ splits $T$ into two components; let $S$ be the one
> containing $u$, so $(S, V \setminus S)$ is a cut that $f$ crosses. The rest of
> the cycle, $C - f$, is a path from $u$ to $v$; it starts in $S$ and ends
> outside, so some edge $e' \in C$ with $e' \neq f$ also crosses the cut. Then
> $T' = T - f + e'$ reconnects the two components: it is a spanning tree, and
> $$
> \text{cost}(T') = \text{cost}(T) - c_f + c_{e'} \le \text{cost}(T),
> $$
> since $f$ is a heaviest edge of $C$. If $T$ was an MST, then $T'$ is an MST
> that omits $f$, proving the first claim. And if $f$ is the strict maximum on
> $C$, the inequality is strict, so $T$ was not minimum to begin with; no MST
> can contain $f$. $\qed$

The fine print matters: the theorem speaks only about edges that lie **on a
cycle**. An edge on no cycle is a bridge, and a bridge is in _every_ spanning
tree no matter how expensive it is. "Heaviest edge of the graph" is not the
same as "heaviest edge on a cycle":

$$
% caption: Left: on the cycle $w$–$x$–$y$–$z$, the strict maximum (weight $8$, dashed) is
%          in no MST. Right: the weight-$9$ edge is the heaviest in its graph, yet it is a
%          bridge, so every spanning tree must include it.
\begin{tikzpicture}[font=\scriptsize,
  V/.style={circle, draw, minimum size=5.4mm, inner sep=0pt, font=\scriptsize},
  wt/.style={font=\scriptsize, inner sep=1.5pt},
  gone/.style={line width=1.3pt, dashed},
  must/.style={line width=1.5pt}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{D1342B}
  % left: 4-cycle, heaviest edge excluded
  \node[V] (w) at (0,1.6) {$w$};
  \node[V] (x) at (2.0,1.6) {$x$};
  \node[V] (y) at (2.0,0) {$y$};
  \node[V] (z) at (0,0) {$z$};
  \draw (w) -- node[wt,above]{$2$} (x);
  \draw (x) -- node[wt,right]{$3$} (y);
  \draw (y) -- node[wt,below]{$4$} (z);
  \draw[gone, draw=red] (z) -- node[wt,left]{$8$} (w);
  \node[red] at (1.0,-0.85) {8 = max on its cycle: in no MST};
  % right: a heavy bridge, forced
  \node[V] (p) at (4.6,1.6) {$p$};
  \node[V] (q) at (4.6,0) {$q$};
  \node[V] (r) at (5.8,0.8) {$r$};
  \node[V] (s) at (7.6,0.8) {$s$};
  \node[V] (t) at (8.8,1.6) {$t$};
  \node[V] (u) at (8.8,0) {$u$};
  \draw (p) -- node[wt,left]{$1$} (q);
  \draw (p) -- node[wt,above right]{$2$} (r);
  \draw (q) -- node[wt,below right]{$3$} (r);
  \draw (s) -- node[wt,above left]{$4$} (t);
  \draw (s) -- node[wt,below left]{$5$} (u);
  \draw (t) -- node[wt,right]{$6$} (u);
  \draw[must, draw=acc] (r) -- node[wt,above]{$9$} (s);
  \node[acc] at (6.7,-0.85) {9 = a bridge: in every MST};
\end{tikzpicture}
$$

Together the two properties settle the uniqueness question.

> **Theorem (Distinct weights make the MST unique).** If no two edges of $G$
> have equal weight, then $G$ has exactly one minimum spanning tree.

> **Proof.** Suppose $T \neq T'$ are both MSTs. Their symmetric difference is
> nonempty; let $e$ be its minimum-weight edge, unique because weights are
> distinct, and say $e \in T \setminus T'$. Adding $e$ to $T'$ creates a cycle
> $C$. Not every edge of $C$ can lie in $T$ (a tree contains no cycle), so some
> $f \in C$ with $f \neq e$ has $f \notin T$; since $C - e \subseteq T'$, this
> $f$ lies in $T' \setminus T$, hence in the symmetric difference, hence
> $c_f > c_e$. Then $T' - f + e$ is a spanning tree strictly cheaper than $T'$,
> contradicting minimality. $\qed$

Distinctness is sufficient but not necessary. The nine-town graph has ties (two
edges of weight $2$, three of weight $7$) yet a unique MST: every one of the
five non-tree edges is the _strict_ maximum on the cycle it closes ($i$–$h$ at
$7$ closes a cycle whose other edges weigh $6$ and $1$; $a$–$h$ at $8$ beats a
path of maximum weight $7$; and so on), so by the cycle property none of them
is in any MST, which forces the remaining eight edges.

## Borůvka's algorithm

The oldest MST algorithm (Otakar Borůvka, 1926) is also the most directly
cut-rule driven, and it parallelises well.[^erickson-mst] The idea: every
component, in every round, _simultaneously_ selects its own cheapest
outgoing edge.

Maintain a forest $A$, initially the $n$ isolated vertices. In each **round**,
each current component $C$ looks at the cut $(C, V \setminus C)$, which respects
$A$, and selects its lightest crossing edge. By the cut property every such edge
is safe, so we add them all at once and merge the components they join. Every
component merges with at least one neighbor, so the number of components at
least halves each round, and only $O(\log V)$ rounds are needed.

```algorithm
caption: $\textsc{Borůvka}(G, c)$ — every component grabs its cheapest exit edge
number: 2
$A \gets \emptyset$ // $n$ singleton components
while $A$ has more than one component do
  foreach component $C$ of $(V, A)$ do
    $e_C \gets$ the lightest edge crossing $(C,\, V \setminus C)$ // safe by cut rule
  foreach distinct edge $e_C$ chosen do
    $A \gets A \cup \set{e_C}$ // add all exit edges at once
return $A$
```

> **Remark (A subtlety).** To keep the result acyclic when weights tie, break ties by a
> fixed total order on edges (e.g. by index). Otherwise two components could pick
> _each other's_ edge as different edges of equal weight and create a cycle.

**Running time.** Each round scans all edges to find component-minimum exits in
$O(E)$ time and there are $O(\log V)$ rounds, so $\textsc{Borůvka}$ runs in
$O(E \log V)$, the same headline bound as Prim and Kruskal, but with the
useful property that the per-round work is fully parallel.

::impl{algo="boruvka"}

One round on six isolated vertices shows the parallel grab. Each singleton (a
component of one) points an arrow along its own cheapest incident edge. Vertices
$a$ and $b$ pick each other (both cheapest at $3$), as do $d$ and $e$ (at $2$)
and $c$ and $f$ (at $4$), so the six arrows name only three distinct edges, and
one sweep merges six components into three:

$$
% caption: One Borůvka round: every component (here singletons) selects its cheapest exit
%          edge (arrows). The three distinct chosen edges merge six components into three.
\begin{tikzpicture}[>=Stealth, font=\small,
  V/.style={circle, draw, minimum size=8mm, font=\small},
  wt/.style={font=\scriptsize, inner sep=1.5pt, fill=white}]
  \definecolor{acc}{HTML}{2348F2}
  \node[V] (a) at (0,1.4) {$a$};
  \node[V] (b) at (2.2,1.4) {$b$};
  \node[V] (c) at (4.4,1.4) {$c$};
  \node[V] (d) at (0,0) {$d$};
  \node[V] (e) at (2.2,0) {$e$};
  \node[V] (f) at (4.4,0) {$f$};
  % undirected edges with weights (thin grey)
  \draw[black] (a) -- node[wt]{$3$} (b);
  \draw[black] (b) -- node[wt]{$5$} (c);
  \draw[black] (a) -- node[wt]{$8$} (d);
  \draw[black] (b) -- node[wt]{$6$} (e);
  \draw[black] (c) -- node[wt,xshift=-3.5mm]{$4$} (f);
  \draw[black] (d) -- node[wt]{$2$} (e);
  \draw[black] (e) -- node[wt]{$7$} (f);
  % each component's cheapest exit, drawn slightly offset
  \draw[->, line width=1.3pt, draw=acc] (a) to[bend left=18] (b);   % a: cheapest 3
  \draw[->, line width=1.3pt, draw=acc] (b) to[bend left=18] (a);   % b: cheapest 3
  \draw[->, line width=1.3pt, draw=acc] (c) to[bend left=26] (f);   % c: cheapest 4
  \draw[->, line width=1.3pt, draw=acc] (d) to[bend left=18] (e);   % d: cheapest 2
  \draw[->, line width=1.3pt, draw=acc] (e) to[bend left=18] (d);   % e: cheapest 2
  \draw[->, line width=1.3pt, draw=acc] (f) to[bend left=26] (c);   % f: cheapest 4
  \node[font=\scriptsize, acc, align=center] at (6.4,0.7)
    {chosen edges\\merge 6 comps\\to 3};
\end{tikzpicture}
$$


## How fast can an MST be found?

The three classical algorithms all land at $O(m \log n)$. Is the log necessary? The answer, developed over decades, is essentially no — and Borůvka's rounds appear in every improvement.

**Borůvka as an accelerator.** A single Borůvka phase costs $O(m)$ and at least halves the vertex count, contracting each component to a single super-vertex. Running $\log \log n$ phases before switching to Prim yields $O(m \log \log n)$; interleaving Borůvka contraction with a Fibonacci-heap priority queue gives Fredman and Tarjan's $O(m \log^\ast n)$ (1987), where $\log^\ast$ — the iterated logarithm — is at most $5$ for any input that fits in the universe.[^ft] The pattern is always the same: use Borůvka to shrink the graph cheaply, then spend the expensive per-edge work on a much smaller instance.

**The randomized linear-time algorithm.** Karger, Klein, and Tarjan (1995) gave an MST algorithm running in $O(m)$ _expected_ time.[^kkt] It alternates Borůvka contraction with a **sampling** step: pick each edge independently with probability $\tfrac{1}{2}$, recursively find the MST of the sample, then use that sample-forest to discard every edge that is _F-heavy_ (heavier than the heaviest edge on the sample-tree path between its endpoints — a cycle-property rejection in bulk). A linear-time MST **verification** procedure certifies the discards, and a sampling lemma bounds the surviving edges by $O(n)$, collapsing the recursion to linear expected work. It is the first MST algorithm to escape the sorting bottleneck entirely.

**The deterministic frontier.** Whether a _deterministic_ linear-time MST algorithm exists is still open. Chazelle (2000) came closest with $O(m\,\alpha(n))$ using a data structure called the soft heap, which deliberately corrupts a few keys to run faster; and Pettie and Ramachandran (2002) gave a provably _optimal_ deterministic algorithm whose exact running time equals the (unknown) decision-tree complexity of the problem — optimal without anyone knowing what that optimum is.[^pr]

$$
% caption: The acceleration pattern behind fast MST algorithms: a Borůvka phase contracts
%          each component to a super-vertex in $O(m)$ time, at least halving $n$, so the
%          expensive work runs on a smaller graph. Repeated contraction drives the log
%          factor down toward a constant.
\begin{tikzpicture}[>=Stealth, font=\small,
  V/.style={circle, draw, minimum size=6mm, font=\scriptsize},
  S/.style={circle, draw, minimum size=8mm, font=\small, fill=acc!15, draw=acc, thick}]
  \definecolor{acc}{HTML}{2348F2}
  % before: 6 vertices in 3 components
  \node[V] (a) at (0,0.8) {}; \node[V] (b) at (0.9,0.4) {};
  \node[V] (c) at (2.0,0.9) {}; \node[V] (d) at (2.9,0.4) {};
  \node[V] (e) at (0.4,-0.6) {}; \node[V] (f) at (1.3,-0.9) {};
  \draw[acc, thick] (a)--(b); \draw[acc, thick] (c)--(d); \draw[acc, thick] (e)--(f);
  \draw[black] (b)--(c); \draw[black] (b)--(e); \draw[black] (d)--(f);
  \node[font=\scriptsize] at (1.4,-1.5) {before: 6 vertices};
  \draw[->, line width=1.2pt, black] (3.6,0.1) -- (4.8,0.1);
  \node[font=\scriptsize] at (4.2,-0.5) {contract};
  % after: 3 super-vertices
  \node[S] (A) at (5.6,0.6) {}; \node[S] (B) at (7.0,0.6) {}; \node[S] (C) at (6.3,-0.6) {};
  \draw[black] (A)--(B); \draw[black] (A)--(C); \draw[black] (B)--(C);
  \node[font=\scriptsize] at (6.3,-1.5) {after: 3 super-vertices};
\end{tikzpicture}
$$

The practical takeaway matches the theory: real fast-MST codes run a couple of Borůvka rounds to shrink the graph, then finish with Prim or Kruskal. This continues in [Kruskal and Prim](/algorithms/graphs/kruskal-and-prim), the two algorithms you will actually implement — one growing a forest with union-find, the other a single tree with a priority queue.

[^clrs-cut]: **CLRS**, Ch. 23 — Minimum Spanning Trees — the generic method, safe edges, and the cut property identifying a safe edge for the greedy MST template.
[^erickson-mst]: **Erickson**, Ch. 8 — Minimum Spanning Trees — the cut and cycle properties, and Borůvka's component-merging rounds in $O(\log V)$ phases.
[^ft]: **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 — the $O(m \log^\ast n)$ MST bound.
[^kkt]: **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 — expected linear-time MST via sampling and Borůvka contraction.
[^pr]: **Pettie, S. & Ramachandran, V.** (2002), "An optimal minimum spanning tree algorithm," _Journal of the ACM_ 49(1), 16–34 — a provably optimal deterministic MST algorithm; and **Chazelle, B.** (2000), "A minimum spanning tree algorithm with inverse-Ackermann type complexity," _JACM_ 47(6), 1028–1047.