1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.