How to prove there always exists a minimax path completely on the MST

Question

A minimax path in an undirected graph is a path between two vertices v, w that minimizes the maximum weight of the edges on the path.

Let T be the minimum spanning tree of a given graph G=(V,E). How can I prove that, for any pair of vertices v, w in V, there always exists a minimax path between v and w that is completely on T.

I have tried to assume there is no minimax path completely on T, but I don't know how to get a contradiction.

Answer 1

Assume there exists a minimax path P between vertices u and v that is not completely on the minimum spanning tree T.

This means there is an edge A(p, q) in P that is not in T.

Let Q be the path in T from p to q.

Let B be an edge with the greatest weight in Q (in the imaged graph the length of the edge represents its weight):

                    T is marked in green
                    P = (u,p,q,v)

There are now 2 conditions to consider:

1. weight(B) > weight(A): In that case T is not a minimum spanning tree. If you would remove B from T and add A instead, you would still have a spanning tree, but its total weight would have decreased. As this is a contradiction (T is given as being a minimum spanning tree), the only possibility left is:

2. weight(B) <= weight(A): In that case you could remove A from P and add the edges from Q to it instead, and it would still be a minimax path, as we did not include an edge with a greater weight than that was already on that path before.

   Note that this replacement will make the minimax path longer, but that is not an issue. There can be several paths between two vertices that all minimise the maximum edge weight -- there is no requirement that the minimax path be the shortest of those.

For every edge A on a minimax path that is not in T, an edge replacement can be done as described in point 2, thereby creating a minimax path that will be completely on T.