= Minimax path property of a minimum spanning tree
Every path in a <minimum spanning tree> solves the <bottleneck shortest path problem> between its endpoints. If $e$ is a maximum-weight edge on the tree path, deleting it gives a <graph cut> separating the endpoints. A competing path with every edge lighter than $e$ would contain a crossing edge $f$; replacing $e$ with $f$ would decrease the tree's total weight, a contradiction. Equal weights cause no problem: the argument excludes a strictly smaller bottleneck and does not require a unique tree.
Back to article page
