Question

Question 2. (15 points; CLO #2): Prove that Prim's greedy algorithm correctly finds the minimum spanning tree when applied to a given undirected weighted graph.

Answer 1

We will prove correctness of prim's greedy algorithm by induction.

Let G be the given undirected weighted graph.

Our inductive hypothesis will be that the tree T constructed so far is consistent with (is a subtree of) some minimum spanning tree (MST) M of G.

This is certainly true at the start.

Now let e be the edge choosen by the algorithm.

We need to argue that the new tree, T U {e} is also consistent with some spanning tree M' of G.

If e belongs to M the we are done (M'=M) .

Else we argue as following :

Consider adding e to M. As above (noted) , this create a cycle.

Since e has one endpoint in T and one outside T, if we trace around this cycle we must eventually get to an edge e' that goes back in to T.

We know len(e') >= len(e) by definition of prim's greedy algorithm.

So if we add e to M and remove e', we get new tree M' that is no longer than M was and contains T U {e}, maintaining our induction and proving the theorem.