Minimax path property of a minimum spanning tree
ID: 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 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 would contain a crossing edge ; replacing with 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.
New to topics? Read the docs here!