Prim's Algorithm - Proof of Correctness

Proof of Correctness

Let P be a connected, weighted graph. At every iteration of Prim's algorithm, an edge must be found that connects a vertex in a subgraph to a vertex outside the subgraph. Since P is connected, there will always be a path to every vertex. The output Y of Prim's algorithm is a tree, because the edge and vertex added to tree Y are connected. Let Y₁ be a minimum spanning tree of graph P. If Y₁=Y then Y is a minimum spanning tree. Otherwise, let e be the first edge added during the construction of tree Y that is not in tree Y₁, and V be the set of vertices connected by the edges added before edge e. Then one endpoint of edge e is in set V and the other is not. Since tree Y₁ is a spanning tree of graph P, there is a path in tree Y₁ joining the two endpoints. As one travels along the path, one must encounter an edge f joining a vertex in set V to one that is not in set V. Now, at the iteration when edge e was added to tree Y, edge f could also have been added and it would be added instead of edge e if its weight was less than e (we know we encountered the opportunity to take "f" before "e" because "f" is connected to V, and we visited every vertex of V before the vertex to which we connected "e" ). Since edge f was not added, we conclude that

Let tree Y₂ be the graph obtained by removing edge f from and adding edge e to tree Y₁. It is easy to show that tree Y₂ is connected, has the same number of edges as tree Y₁, and the total weights of its edges is not larger than that of tree Y₁, therefore it is also a minimum spanning tree of graph P and it contains edge e and all the edges added before it during the construction of set V. Repeat the steps above and we will eventually obtain a minimum spanning tree of graph P that is identical to tree Y. This shows Y is a minimum spanning tree.