**Problem2D: Here is a variation on the above greedy algorithm. Let **** be any vertex of a weighted connected graph **** with **** vertices and let **** be the subgraph with the one vertex **** and no edges. After a tree (subgraph) ****, ****, has been defined, let **** be a cheapest edge among all edges with one end in **** and the other end not in ****, and let **** be the tree obtained by adding that edge and its other end to ****. Prove that **** is a cheapest spanning tree in ****.**

**Solution:** This algorithm is called Prim’s algorithm. The proof can be found in Wikipedia. We state the proof here again. Suppose is a cheapest spanning tree. If , the proof finished. Otherwise, let be the first edge not in when we generate Denote by all the edges before we add . Since is a spanning tree, there is a unique cycle in containing two ends of . We claim that there is at least one edge having one end in , and the other end not in . Otherwise, if all the vertices of the cycle are in , will contain a cycle, a contradiction. On the other hand, not all the vertices are outside of since one end of is in . So there must exists at least one edge having one end in and the other not in . By Prim’s algorithm, , otherwise would be chosen rather than . Add to and delete , we obtain a new spanning tree which is still a cheapest spanning tree. Keep doing this until we obtain a cheapest spanning tree identical to ,

**Note: **The hint in the book says that has the property that for every edge in , the ends of are in different components of . And any spanning having this property will be a cheapest spanning tree. I still do not know how to show the second part. I shall be happy if anyone can suggest the solution.