Minimum Spanning Tree

Definition (Minimum Spanning Tree)

Given graph $G$ with weight function $w:E\to \mathbb{R}$, we want the spanning tree $T$ where

$$\sum _{e\in E}w(e)$$

is as small as possible.

Lemma (Constructing MST by Lightest Edge)

If $G$ is a finite weighted connected graph, and $e$ is the minimum weight edge of $G$, then $G$ has a MST containing edge $e$.

In fact, if $e$ is the unique lightest edge, then all MSTs contain $e$.

Proof (1): Let $G$ be a weighted, connected graph and let $e=(u,v)$ be an edge with the minimum weight in $G$. Let $T$ be any MST of $G$.

If $e\in T$, the lemma holds and we are done.

If $e\notin T$, then we can find a new spanning tree $T^{\prime }$ where $e\in T^{\prime }$ and $w(T^{\prime })\le w(T)$. If $T$ was minimal, then so is $T^{\prime }$.

Then if we add $e$ to $T$, then as $u,v$ were already connected (by definition of a Tree), this creates a cycle $C_e$, and so we no longer have a tree. Cycle $C_e$ must have some other edge $e^{\prime }\ne e$ where

$$w(e)\le w(e^{\prime })$$

and

$$T^{\prime }=T\cup \{e\}-\{e^{\prime }\}$$

This $T^{\prime }$ is a spanning tree. We know $T\cup \{e\}$ is connected. If we remove $e^{\prime }$ from $C_e$ then we still have a connected graph. In particular, this shows $T^{\prime }$ is a connected graph. But,

$$|E(T^{\prime })|=|E(T)|=|V|-1$$

then we must have no cycles by Lemma (Tree Edge Count). Therefore, $T^{\prime }$ is a tree.

Now we can work with $T^{\prime }$. Next,

$$w(T^{\prime })=w(T)-w(e^{\prime })+w(e)$$

But then

$$\begin{array}{rl}w(e)\le w(e^{\prime })& ⟺w(e)-w(e^{\prime })\le 0\\ & ⟺w(T^{\prime })\le w(T)\end{array}$$

But then $T$ was already an MST, then $T^{\prime }$ must also be an MST.

If $e$ was the unique lightest edge, then $w(e)<w(x)$ for any other edge $x\ne e$. Then strictly,

$$w(T^{\prime })<w(T)$$

indeed, all MSTs must contain $e$.

Graph Contraction

When we construct an edge $e=(u,v)$ to our MST, we can treat $u,v$ as the same vertex, combining the previous vertices of the edge. We can repeat our construction by selecting the lightest remaining edge in lemma.

Where remaining means an edge that does not form a cycle.