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 be a spanning tree of and , the longest edge in a spanning tree.
MSTT, so L(MST) cannot be less than the minimum L(T) of all T’s.
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, and . 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 because it’s from some vertex to . If it’s the max edge of its spanning tree, . . If it’s not, there exists a max edge in such that . So .