Page 298 Exercise 1

To demonstrate that Prim's algorithm produces a minimum spanning tree, we must verify that  1) a tree is formed, and 2) it has the lowest weight. 

We can easily demonstrate that Prim's algorithm creates a directed, acyclic graph, and, hence, a tree.  First, we note that, at each stage, the algorithm adds an edge only if one of its vertices is already in the tree.  Thus, the graph is always connected.  Because the algorithm does not add a vertex if the other vertex incident to the edge has the same root, cycles are avoided.  In addition, since exactly n-1 edges are added to the tree, the graph connect all vertices. 

The graph intuitively is of minimum weight because each stage adds the lowest weight  unprocessed edge with a vertex in the tree.  Since the lowest weight edges are always picked, the final result must be minimal.