Does there exist some connected undirected graph G with positive edge weights w such that G has a shortest path tree S and a minimum spanning tree T that do not share any edges? Prove your answer.

A. Yes, it is always possible.
B. No, it is never possible.
C. It depends on the graph G.
D. It depends on the edge weights w.

Q&A Education