Given a connected, undirected graph G, edge-weighted (positive), prove that
If G has a spanning tree T which, for each vertex r in G, is a shortest path tree from r, then G has a unique MST.
I know how to show that given a T like that, it is also a MST, but how can I show that it's unique? I tried to assume by contradiction that it isn't, but I can't see how to get a contradiction from that
Here is a hint:
Pick any edge $e$ not in $T$. If you add $e$ to $T$, you will get a cycle. Can you show that $e$ is the unique heaviest edge in that cycle?
If you have seen the above hint, it is unlikely that you will not be able to complete what that hint ask you to do. In case you are still wondering what to do next, here is the hint for the next step.
You are almost done! Can an MST contain the unique heaviest edge in any cycle?
