Minimum spanning tree

A spanning tree of a graph $G=(V,E)$ is the graph that contains a subset $S\subseteq E$ of edges and all vertices of $G$. It is the minimum number of edges we need to make sure that the graph remains connected.

Often this subset of edges is called $T$, which we also use to mean the overall tree that is constructed. An abuse of notation.

If each edge also carries a cost/weight specified by $w:E\to \mathbb{R}$, then the minimum spanning tree is the spanning tree of $G$ that minimizes the total weights of all the edges chosen.

There are many algorithms for Finding the minimum spanning tree, and they run surprisingly fast (for me, at least). They utilize some properties about MSTs that allow us to claim when an edge is included, and when it’s discarded.

Cut property

Let $G=(V,E)$ be any connected graph, and let $S$ be a non-empty subset of $V$. Then the following must be true:

• There exists an edge $e=(u,v)$ such that $e\in E$ and $u\in S,v\in V-S$.
• There exists a minimum weight edge $e$ that must exist in $\text{OPT}$, a minimum spanning tree for $G$.

We can prove this using an Exchange argument: given $\text{OPT}$, we consider the same cut $S$. If our tree $\text{OPT}$ contains the minimum weight edge $e=(u,v)$, then we’re already done.

If it does not exist in $\text{OPT}$, then we can exchange an edge $e^{\prime }$ with $e$. This can only decrease the overall cost, because we defined $e$ to be the minimum weight edge that cross the cut. Furthermore, ${\text{OPT}}^{\prime }$ remains a tree because the number of edges across this cut remains one.

This implies that $\text{OPT}$ was never the MST for $G$, and we have a contradiction. Therefore, the MST for $G$ must include edge $e$.

Cycle property

Let $G=(V,E)$ be a connected, undirected graph that contains at least one cycle. Let $C$ be any cycle in $G$ and let edge $e$ be the heaviest weight edge in $C$. Then, $e$ does not exist in some MST of $G$.

We can essentially prove this with another exchange argument. Assume for contradiction that a MST of $G$ does contain the heaviest weight edge $e$ in some cycle $C$. Then, we can exchange $e$ with some other edge $e^{\prime }$ that does not exist in the MST, and is part of $C$.

• MST remains a tree because we removed an edge and added another in the same cycle.
• By definition, $w(e^{\prime })<w(e)$, and so the overall weight of the new MST can only decrease.

Therefore, the old MST did not have the minimum overall weight, which is a contradiction. So, $e$ cannot be part of some MST for $G$.