The Safe-Edge Theorem

The safe-edge theorem is the correctness foundation for all greedy MST algorithms. It formalises the cut property into a constructive rule: given a partial MST, any light edge crossing a cut that respects the current edge set can be safely added.

Formal Statement

Let $G = (V, E)$ be a connected undirected graph with weight function $w$.

Let $A \subseteq E$ be a subset of some MST.

Let $(S, V \setminus S)$ be any cut of $G$ that respects $A$ (no edge in $A$ crosses the cut).

Let $(u, v)$ be a light edge crossing $(S, V \setminus S)$ (minimum weight among all crossing edges).

Then $(u, v)$ is a safe edge for $A$: $A \cup \{(u, v)\} \subseteq T'$ for some MST $T'$.

Proof (Full)

Let $T$ be an MST containing $A$. If $(u, v) \in T$, we are done ($T' = T$).

Otherwise, $(u, v) \notin T$. Since $T$ is a spanning tree, there is a unique path $p$ from $u$ to $v$ in $T$. Because $(u, v)$ crosses the cut, and $T$ connects all vertices, the path $p$ must cross the cut at least once. Let $(x, y)$ be an edge on $p$ that crosses the cut.

Now $(x, y) \notin A$, because the cut respects $A$ (no edge of $A$ crosses it).

Consider $T' = T \setminus \{(x, y)\} \cup \{(u, v)\}$:

• $T'$ is connected (removing $(x, y)$ splits $T$ into two components; adding $(u, v)$ reconnects them, since $u$ and $v$ are in opposite components)
• $T'$ is acyclic (adding $(u, v)$ to $T$ created one cycle; removing $(x, y)$ breaks it)
• $T'$ has $|V|-1$ edges, so it is a spanning tree

Weight comparison:

$w(T') = w(T) - w(x, y) + w(u, v) \le w(T)$

The inequality follows because $(u, v)$ is a light edge crossing the cut, so $w(u, v) \le w(x, y)$.

Since $T$ is minimum, $w(T') \ge w(T)$. Combined, $w(T') = w(T)$, so $T'$ is also an MST.

$A \subseteq T$ and $(x, y) \notin A$, so $A \subseteq T \setminus \{(x, y)\} \subset T'$. Also $(u, v) \in T'$. Hence $A \cup \{(u, v)\} \subseteq T'$, proving $(u, v)$ is safe. $\square$

Corollary

Let $G_A = (V, A)$ be the forest formed by the current edges (initially $A = \emptyset$, so $G_A$ has $|V|$ isolated vertices). If $(u, v)$ is a light edge connecting two distinct components of $G_A$, then $(u, v)$ is safe.

Proof: For any component $C$ of $G_A$, the cut $(C, V \setminus C)$ respects $A$ (since $A$ only contains edges within components, never between them). A light edge connecting $C$ to another component crosses this cut, so by the safe-edge theorem, it is safe.

How Kruskal and Prim Use It

• Kruskal: processes edges in increasing weight order. When considering edge $(u, v)$ connecting two different trees in the forest $G_A$, it crosses the cut $(C_u, V \setminus C_u)$ where $C_u$ is the component containing $u$. Since edges are processed in weight order and no lighter edge could still connect these components, $(u, v)$ is a light edge for that cut, hence safe.

• Prim: grows a single tree from a root. At each step, the edge of minimum weight connecting a vertex in the tree to a vertex outside is a light edge crossing the cut (tree, rest-of-graph). Hence safe.

Summary

Term	Definition
Respects $A$	No edge in $A$ crosses the cut
Light edge	Minimum weight among edges crossing a given cut
Safe edge	Adding it preserves the invariant “subset of some MST”
Proof technique	Swap argument: replace a crossing edge in $T$ with the light edge

Past Tripos: y2024p2q7, y2023p1q9.