Consider the following divide-and-conquer algorithm for determining minimum spanning trees.
Suppose G is an undirected, connected, weighted graph with distinct edge weights. If G is a single
vertex, then the algorithm just returns, outputting nothing. Otherwise, it divides the set of vertices
of G into two sets, Vi and V2, of nearly equal size. Let e be the minimum-weight edge in G that
connects V1 and V2. Output e as belonging to the minimum spanning tree. Let G1 be the subgraph
of G induced by V1 (that is, G1 consists of the vertices in V1 plus all the edges of G that connect
pairs of vertices in V1. Similarly, let G2 be the subgraph of G induced by V2. The algorithm is then
recursively executed on G1 and G2. Does this algorithm output exactly the edges of the minimum
spanning tree of G? If the algorithm is correct, prove its correctness. If not, give a counterexample
to prove that the algorithm is incorrect.