Given a connected undirected graph G(V, E) with positive weights on the edges. Assume that we found all shortest paths from a starting node s to the other vertices. (e.g. by using Dijkstras or some other algorithm) The union of these paths forms a tree, which we will call the shortest paths tree or SPT at s. Note, that a graph may have multiple SPTs.

1. (10 pts.) Give an example of a weighted graph, whose minimum spanning tree (MST) differs from all its SPTs. In your answer make it clear what the edges and weights of the graph are. (e.g. legible picture or specify the edge list) Also specify what the MST and SPTs are. We recommend you find a small example as you need to list all possible trees.

2. (10 pts.) Prove that an MST and an SPT of G always have at least one edge in common.