Will a minimum spanning tree and shortest path tree always share at least one edge?

Question

I'm studying graph theory and I have a question about the connection between minimum spanning trees and shortest path trees.

Let G be an undirected, connected graph where all edges are weighted with different costs. Let T be an MST of G and let T_s be a shortest-path tree for some node s. Are T and T_s guaranteed to share at least one edge?

I believe this is not always true, but I can't find a counterexample. Does anyone have a suggestion on how to find a counterexample?

Answer 1

I think that this statement is actually true, so I doubt you can find a counterexample.

Here's a hint - take any node in the graph and find a shortest path tree for that node. Now consider what would happen if you were to run Prim's algorithm starting from that node - can you guarantee that at least one edge from the MST will find its way into the shortest path tree?

Hope this helps!