For a graph G V E let us define as promising any subset F o

For a graph G = (V, E), let us define as promising any subset F of E if edges can be added to it to complete it into a minimum spanning tree. The following is a useful lemma regarding such sets: If a set F is promising and e is the edge of least weight connecting a vertex in V - F with one inside F, then F U (e) is promising. Using this lemma, prove the correctness of Prim?s Algorithm. Do not forget that this includes a proof of termination, however simple.

Solution

we will prove it by contradiction.so suppose prim\'s algoritm fails. Consider the first edge \"e\" chosen by the algorithm that is not consistent with an MST. Let T be the tree we have made just before adding in e, and let M be the MST which is consistent with T. Now, assume we add e to the M. This creates a cycle. As e has one endpoint in T and one outside T, if we move around this cycle we must eventually get to an edge e1 that goes back in to T. We know length(e1) >= length(e) by definition of the algorithm. So, if we add e to M and remove e1, we come up with a new tree that is no larger than M was, contradicting our definition of \"e\".