MST

We are concerned with MSTs of a connected graph $G$.

A light edge of a cut $c=[S,V(G)-S]$ is an edge with minimum weight among all edges crossing $c$. A heavy edge of a cycle $C$ is an edge of maximum weight among all edges of $C$.

Lemma. An edge $e$ is in some MST $\Leftrightarrow e$ is a light edge of some cut.

Proof:

$(\Rightarrow)$ Remove $e$ from MST $T$ to get a cut $c$. If $e$ is not a light edge of $c$ then $w(T-e+f)<w(T)$ where $f$ is a light edge of $c$.

$(\Leftarrow)$ If MST $T$ does not have $e$, then $T+e$ has a cycle $C$ crossing $c$ at least twice, once at $e$ and another at $f$. $T-f+e$ is also a MST.

Lemma. Every MST $T$ contains a light edge of every cut $c$.

This implies that Prim's algorithm can produce all MSTs as follows. Start from an arbitrary vertex $v$ and set $S=\{v\}$, make the algorithm pick the light edge $vu$ of $[S,V(G)-S]$ that is also in $T$ and add $u$ to $S$. Repeat until $T$ is obtained.

Proof: If not, for light edge $e$ of $c$, $T+e$ has a cycle $C$ crossing $c$, once at $e$ and once at $f$, and $w(e)<w(f)$. So $w(T+e-f)<w(T)$, contradiction.

 

Lemma. An edge $e$ is not in some MST $\Leftrightarrow e$ is a heavy edge of some cycle.

Lemma. For every MST $T$, every cycle $C$ has a heavy edge not in $T$.