Review 5: Minimum spanning trees: Questions
Indicate a minimum spanning tree of the below graph.
![](mst1.png)
Suppose we were to execute Prim's algorithm beginning at the center bottom vertex. In what order would edges be added to the minimum spanning tree?
![](mst1.png)
Suppose we were to execute Kruskal's algorithm beginning at the center bottom vertex. In what order would edges be added to the minimum spanning tree?
![](mst1.png)
Give an example of an undirected, weighted graph for which there is a pair of vertices s and t where the shortest path from s to t does not lie within the graph's minimum spanning tree. Justify your answer.
Review 5: Minimum spanning trees: Solutions
![](mst1-soln.png)
![](mst-path.png)
In the above graph, there is just one minimum spanning tree, which includes the edges labeled 2 and 3. However, the shortest path from s to t is to take the edge of length 4, which is not included in the minimum spanning tree.