Is there always some MST that is a shortest path tree?

Question

In my computer science course our professor gave us this final exam problem, and I'm having trouble:

Marissa and Joel are going on a road trip and they want to make sure they stop in each city (think of the streets as the edges of the graph and the cities as the vertices). They want to reach each city, and they will be starting in their hometown city, Vertexville, NY. They want to be as fuel efficient as possible, and don’t like seeing the same scenery twice, so they require that the highways/roads traversed in their possible road trip routes be a concept called a shortest path tree (in other words, the roads traversed in their possible routes be acyclic).

You are helping Marissa and Joel plan their trip, and they have are testing you for your computer science final in doing so, so they ask you:

Is it possible to have a minimum spanning tree and a shortest path tree such that the MST and the SP tree are completely edge-disjoint?

You found an MST for their road trip. They want to know if for every graph, there always exists an MST that is an SP tree?

-Roads/highways are bi-directional (graph is undirected)

-All edge lengths are positive and distinct

Is there a proof to show this that isn't just constructing a counterexample??

Answer 1

Is it possible to have a minimum spanning tree and a shortest path tree such that the MST and the SP tree are completely edge-disjoint?

No. Construct any SP tree. The shortest edge from the SP root will always be in both the SP tree and the MST. Proof:

Let the SP root be A and let AC be the shortest adjacent edge. Obviously AC is the shortest path to C, so it will be in the SP tree.

There is exactly one MST. [proof]   If we build it with Kruskal's algorithm, then AC is the first visited edge that can connect A to anything else. Therefore it will be in the MST as well.

They want to know if for every graph, there always exists an MST that is an SP tree?

No. For example, a ring of more than 5 vertices connected with edges of length 1, and all other pairs of vertices connected with edges of length 2. Every MST will contain only edges of length 1 (all but one ring edges), while every SP tree will contain at least one edge of length 2 (a shortcut).

Note that this construction works just as well for distinct weights (as specified in the question) that differ from the above proportions by relatively insignificant amounts -- weights 1000, 1001, 1002, ... and 2000, 2001, 2002... etc.

Is there a proof to show this that isn't just constructing a counterexample??

Maybe, but counterexamples are the best way to prove a negation, because they don't require any fancy reasoning.