Given an undirected, weighted graph G(V,E), consider the following algorithm to find the minimum spanning tree. This algorithm is similar to Prims, except rather than grow out a spanning tree from one vertex, it tries to grow out the spanning tree from every vertex at the same time.

procedure FindMST(G(V, E))

T

while T is not a spanning tree do Let S1, S2 . . . Sk be the components of the graph with vertices V and edges T. For each i, let ei be the minimum-weight edge with exactly one endpoint in Si T T {e1,e2,...ek}

return T

For simplicity, in the following parts you may assume that no two edges in G have the same weight.

a) Show that this algorithm finds a minimum spanning tree.

b) Give an exact upper bound (that is, an upper bound without using Big-O notation) on the worst-case number of iterations of the while loop in one run of the algorithm.

c) Using your answer to the previous part, give an upper bound on the runtime of this algorithm.