Page 298 Exercise 3

As was true of Prim's and Kruskal's algorithms, we must demonstrate that Sollin's algorithm produces a connected, acyclic graph of minimum weight.  The explanation of the that appears in Page 299, Problem 7 furnishes much of the required proof, and I will only elaborate here.

Sollin's alogorithm, like Kruskal's, creates a spanning forest which eventually forms a tree, if one exists.  Unlike Kruskal's algorithm, several edges are selected for inclusion in each pass.  At each stage, edges are selected only if the two vertices of the edge do not share the same root.  An edge whose vertices share a root is a back edge.  Such  an edge will produce a cycle.   Edges incident to all vertices are selected at each stage.  Thus, the graph must connect all vertices.  Since exactly n-1 edges are selected for inclusion in the final graph,  the graph is also acyclic.

Because the edges are maintained in ascending order, and because an edge is excluded from consideration only if both vertices already have edges represented  at that stage, a minimal graph is produced.  That is, an edge whose vertices have already been selected must have a higher weight, since an edge is selected
only if its weight is the lowest for each of its vertices.