# 25.5 MST Exercises
## Factual
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.
Problem 1
Only B. C and D have cycles; A does not span all vertices.
Problem 2
True. In a tree, there is only one SPT and MST.
## Procedural
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.
Problem 1
Order: `A B D C F G E`. Prim's repeatedly picks the lightest edge between the current tree and any node not in the tree.
Problem 2
`AB, BD, CF, FG, AC, EG`. Kruskal's keeps adding the next lightest edge as long as it doesn't form a cycle.
Problem 3
Simply take the logarithm of each edge weight, then run any MST algorithm on it. This is guaranteed to work since $$\log a + \log b = \log ab$$, and minimizing the logarithm of the product is the same as minimizing the product for positive weight edges.
## Metacognitive
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.
Problem 1
Adding 1 to each number will not change the order of the edges when we sort them, therefore we will get the same MST.
Problem 2
False. A counterexample is the following graph:
Prim’s starting from A will select AD, BD, and CD, whereas Kruskals will select AD, BC, and BD.
Problem 3
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.
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://cs61b-2.gitbook.io/cs61b-textbook/25.-minimum-spanning-trees/25.5-mst-exercises.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.