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$.

Uniqueness of edge weight multiset of MST

A connected graph $G$ may have multiple MSTs. However, the multiset of MST's edge weight is unique!

=============================================

Proof

Let $T_1$ and $T_2$ be distinct MSTs of $G$. Consider $e_1\in E(T_1)-E(T_2)$. By this, there exists $e_2\in E(T_2)-E(T_1)$ such that both $T_3=T_1+e_2-e_1$ and $T_4=T_2+e_1-e_2$ are spanning trees of $G$. This implies that $w(e_1)=w(e_2)$, and both $T_3$ and $T_4$ are MSTs of $G$. Moreover $T_4$ and $T_2$ have the same edge weight multiset. Now rename $T_4$ as $T_2$, find another edge $e'_1\in E(T_1)-E(T_2)$, and apply the same tool. Eventually we can show that all these MSTs have the same edge weight multiset.

Beautiful cut and cycle argument

Let $T_1$, $T_2$ be distinct spanning trees of a connected graph $G$. For that for every $e_1 \in E(T_1)-E(T_2)$, there is an edge $e_2 \in E(T_2)-E(T_1)$ such that both $T_2+e_1-e_2$ and $T_1-e_1+e_2$ are spanning trees of $G$.

==============================================

Proof

$T_2+e_1$ has an unique cycle $C$, while $T_1-e_1$ has two components $D_1$ and $D_2$. $C$ crosses the boundary of $D_1$ and $D_2$ at least twice, once at $e_1$. Any other edge of $C$ that crosses that boundary can be $e_2$.