= Solution
Take a <minimum spanning tree> $T$, for example one constructed by <Kruskal's algorithm>. Fix $v$ and let $e$ be a longest edge of the tree's unique $xv$ path. Deleting $e$ partitions $T$ into two components separating $x$ and $v$. Any alternative $xv$ path crosses this <graph cut>. If all of its edges were shorter than $e$, a crossing edge $f$ would let us replace $e$ by $f$, producing a <spanning tree> of smaller total length. This contradicts minimality of $T$.
Therefore every competing path has an edge at least as long as $e$, and the tree path solves the <bottleneck shortest path problem>. The same <minimum spanning tree> works simultaneously for every $v$; this is the <minimax path property of a minimum spanning tree>.
Back to article page
