Prove that Prim's algorithm produces a minimum spanning tree of a connected weighted graph.

Ans: Suppose G be a connected, weighted graph. At each iteration of Prim's algorithm, an edge should be found that connects a vertex in a subgraph to a vertex outside the subgraph. As G is connected, there will all time be a path to each vertex. The output T of Prim's algorithm is a tree, as the edge and vertex added to T are connected. Suppose T₁ be a minimum spanning tree of G. If T₁=T then T is a minimum spanning tree. If not, let e be the first edge added throughout the construction of T that is not in T₁, and V be the set of vertices connected by the edges added previous to e. After that one endpoint of e is in V and the other is not. As T₁ is a spanning tree of G, there is a path in T₁ joining the two endpoints. As one travels along with the path, one should encounter an edge f joining a vertex in V to one that is not in V. Now here, at the iteration while e was added to T, f could as well have been added and it would be added in place of e if its weight was less than e. As f was not added, we conclude that w(f) ≥ w(e).

Suppose T₂ be the graph acquired by removing f and adding e from T₁. It is simple to show that T₂ is connected, has similar number of edges as T₁, and the total weights of its edges is not larger as compared to that of T₁, therefore it is as well a minimum spanning tree of G and it consists of e and all the edges added before it throughout the construction of V. Repeat the steps above and we will eventually acquired a minimum spanning tree of G that is similar to T. This depicts T is a minimum spanning tree.