Widest path algorithm proof of correctness

Question

How do you prove that that the maximum spanning tree of an undirected graph will contain the path that is the widest path between any two vertices A and B in the graph?

I have tried thinking about the proof for Kruskal's algorithm with an edit so it produces the maximum spanning tree but I do not see why the maximal spanning tree must contain the edges in the widest path especially if there are multiple widest paths.

Well, when considering the proof of Kruskal's algorithm, you know that it results in a Minimum Spanning Tree, so what happens when you take the inverse of this algorithm and sort the edges in descending order? — Evan Bechtol, Jun 08 '16 at 19:36
Possible duplicate: http://stackoverflow.com/a/4992766/4515720 — Evan Bechtol, Jun 08 '16 at 19:36
I am using Kruskal's with edges sorted so it returns a Maximum Spanning Tree. — SuspiciousPineapple, Jun 08 '16 at 22:23
I want to show the widest path comes from the maximum spanning tree. — SuspiciousPineapple, Jun 08 '16 at 22:29
Possible duplicate of [Widest path algorithm](http://stackoverflow.com/questions/37632036/widest-path-algorithm) — beaker, Jun 08 '16 at 23:37

score 1 · Answer 1 · answered Jun 09 '16 at 01:00

Proofs about optimality are often by contradiction. Here you'd set yourself up to find one by saying

Suppose there are vertices A and B with a widest path between them containing at least one edge not in any maximum spanning tree of the graph.

Now you must show that the existence such an edge leads to the desired contradiction. One clear path would be to show that this edge can be used to construct a new spanning tree of weight greater than any of the graph's maximum spanning trees. Therefore they weren't maximum after all.

The existence of a contradiction shows that the hypothetical widest path from A to B doesn't exist. Therefore the proof is at hand.

Widest path algorithm proof of correctness

1 Answers1