Consider the following divide and conquer algorithm that claims to find an MST when the input is a

complete graph G with positive edge weights:

Algorithm Description: Given an undirected complete graph G $=($V$,$ E$)$ with positive edge weights

where V $=[$v$1,...,$ vn$],$

$$ If n $=1$ then return the empty set of edges.

$$ Otherwise, split the set of vertices into two sets: V $=[$v$1,...,$ v$$n$/2]$ and V $=[$v$$n$/2+1,...,$ vn$].$

$$ Create two new graphs G$=($V $,$ E$)$ and G$=($V $,$ E$)$ where E$$ E is the set of edges with

both endpoints in V $$ and E$$ E is the set of edges with both endpoints in V $.$

$$ Recursively run the algorithm on G$$ and G$$ to get T $$ and T $,$ respectively. Find the lightest

edge that connects a vertex in T $$ to a vertex in T $$ and call that edge e$.$

$$ Return T $\backslash$cup T $\backslash$cup $\{$e$\}.$

Disprove the correctness of this algorithm by giving a counterexample. $(8$ points$)$