Comment on page
25.5 MST Exercises
- 1.Select all valid MSTs in the diagram below.

- 2.True/False: It is possible that the only Shortest Path Tree is the only Minimum Spanning Tree.
- 1.Run Prim's from
A
in the graph below. In what order are vertices visited? Break ties alphabetically. - 2.Run Kruskal's in the graph below. In what order are edges added to the tree? Break ties alphabetically.

- 3.Design an algorithm to find the min-product spanning tree; ie the spanning tree with the minimum product of its edges. You may assume all edge weights are > 1.
- 1.If we add 1 to the weight of each edge in an arbitrary graph, will the MST created by Kruskal’s change?
- 2.True/False: Prim’s Algorithm and Kruskal’s algorithm will always return the same result. If this is true, explain why. If this is false, provide a counterexample, breaking ties alphabetically.
- 3.Prove the following, known as the cycle property: Given any cycle in an edge weighted graph (all edge weights distinct), the edge of maximum weight in the cycle does not belong to the MST of the graph.
Suppose, for contradiction, the maximum-weight edge
f
in a cycle is present in the MST.

Removing
f
disconnects our MST T
. Form a cut with the two sides of the MST after f
is removed.Since
f
is part of a cycle, there must be also some edge e
crossing that same cut. However, if we replace f
with e
, we now have a spanning tree that has less weight than our MST T
.This is a contradiction, so the maximum weight edge in a cycle cannot be part of the MST.
Last modified 8mo ago