### Minimum spanning tree exercises

Review the proof of correctness for Kruskal's algorithm: MinimumSpanningTreesByKruskals .

#### (i) Prim's algorithm:

0. Input: weighted graph G=(V,E). Output: MST S.
1. Choose any "start" vertex s and let C = {s}.
2. Let S={}.
3. Until C == V do
4. From all the edges leaving C, choose a minimum-weight one (u,w).
5. Add w to C.
6. Add (u,w) to S.
7. Return S.

claim: Prim's algorithm is correct. That is, given any connected weighted graph, the algorithm returns a minimum spanning tree.

exercise: prove or disprove the claim.

stepping stone: prove that the first edge chosen by the algorithm is in some MST

#### (ii) cycle-breaking algorithm

1. While the graph contains cycles do:
2. Find a cycle C.
3. Find a maximum-weight edge e on C.
4. Delete e from the graph.
5. Return the tree formed by the remaining edges.

claim: This algorithm is correct. That is, given any connected weighted graph, the algorithm returns a minimum spanning tree.

exercise: prove or disprove the claim.

stepping stone: prove that there is an MST that does not contain the first deleted edge

#### (iii) uniqueness of MSTs

claim: In any connected, weighted graph with distinct edge weights (no two edges have the same weight), there is exactly one minimum spanning tree.

exercise: prove or disprove the claim.

stepping stone: prove that if the min-wt edge is unique, then every MST contains it

### References