Problem Statement: Consider a path between two vertices in a undirected weighted graph G. The width of this path is the minimum weight of any edge in the path. Prove that the maximum spanning tree of G contains widest paths between every pair of vertices.
More detailed explanation can be found here: https://en.wikipedia.org/wiki/Widest_path_problem#Undirected_graphs
I have tried to prove it by Mathematical Contradiction. Let there exists vertices U and V with a widest path between them containing at least one edge not in any maximum spanning tree of graph.
Somehow, if we can prove that this edge can be used to construct a new spanning tree of weight greater than any of the graph's MSTs, then our supposition was wrong and hence proved.
Now, I am stuck in proving the above.
Best Answer
Let's say we had a spanning tree of our graph which had a suboptimal path between two nodes. Suppose then we were to remove the edge with the lowest weight on that path: by virtue of trees having no cycles, there is now no path connecting the two points.
Suppose now we were to add an edge from the widest path into the spanning tree in a place that it won't cause a cycle. We're guaranteed to be able to add an edge without causing a cycle because there is currently no path between the two nodes, so every path between our two nodes must contain some edge between two previously unconnected nodes.
The weight of the edge we removed was equal to the width of the original path, and because the path was suboptimal we know that every edge in the new path must have had more weight than that edge. This means that our new spanning tree must have strictly more total weight than the original, which contradicts the definition of the original "maximum" spanning tree.