Divide and Conquer MST Consider the following divide-and-conquer algorithm for computing minimum spanning trees. The intuition is that we can divide a graph into half, solve the MST problem for each...

Extracted text: Divide and Conquer MST Consider the following divide-and-conquer algorithm for computing minimum spanning trees. The intuition is that we can divide a graph into half, solve the MST problem for each half, and then find a minimum cost edge spanning the two halves. More formally: Given a graph G = (V, E), partition the set V of vertices into two sets V, and V, such that |V,| and |V,| differ by at most 1. Let E, be the set of edges that are incident only on vertices in V, and let E, be the set of edges that are incident only on vertices in V,. Recursively solve a minimum-spanning-tree problem on each of the two subgraphs G, = (V,, E,) and G, (V, E;). Finally, select the minimum-weight edge in E that crosses the cut (V, V,) and use this edge to unite the resulting two minimum spanning trees into a single spanning tree. Prove that this algorithm correctly computes a minimum spanning tree of G, or provide an example for which the algorithm fails.