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.
Articles by others on the same topic
There are currently no matching articles.