Minimum Spanning Tree

My attempt to reconstruct a detailed proof for a remark on Luc Devroye’s note of MST.

Max edge in a spanning tree

Let $T$ be a spanning tree of $G(V,E)$ and $L(T) = max_{(u,v)\in T}\ w[u, v]$, the longest edge in a spanning tree.

$\text{Claim: The minimum spanning tree also minimizes L(T), that is, }$

$\text{Proof:}$

”$\geq$”

MST$\in$T, so L(MST) cannot be less than the minimum L(T) of all T’s.

”$\leq$”

In the figure above, we assume the red arrow is the longest edge in MST. We construct the MST by adding the shortest “bridge” each time we cross two sets, $A$ and $V-A$. Thus, all other grey edges are longer than or equal to the red edge. These grey edges are in some other spanning trees.

For convenience, take one grey edge and call it $(x,y)$ because it’s from some vertex $x\in A$ to $y \in V-A$. If it’s the max edge of its spanning tree, $T_x$. $L(T_x) \geq L(MST)$. If it’s not, there exists a max edge $(x',y')$ in $T_x$ such that $(x',y') \gt (x, y) \geq L(MST)$. So $L(T_x) \geq L(MST)$.

Q.E.D