Skip to content

Sixian Li

Minimum spanning tree

Algorithm

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

Max edge in a spanning tree

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

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

L(MST)=minall TL(T)L(MST) = min_{all\ T} L(T)

Proof:\text{Proof:}

mst.png

\geq

MST\inT, 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, AA and VAV-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)(x,y) because it’s from some vertex xAx\in A to yVAy \in V-A. If it’s the max edge of its spanning tree, TxT_x. L(Tx)L(MST)L(T_x) \geq L(MST). If it’s not, there exists a max edge (x,y)(x',y') in TxT_x such that (x,y)>(x,y)L(MST)(x',y') \gt (x, y) \geq L(MST). So L(Tx)L(MST)L(T_x) \geq L(MST).

Q.E.D