Let G = (V,E) be a connected, undirected, weighted graph. Consider the following Divide and Conquer Algorithm to build a MST of G. (You may assume that |V| is a power of 2)

- If |V| = 2, return the edge which connects them. (In our class, unless otherwise stated, we assume all graphs are simple)

- Else

- Partition V into two disjoint sets of equal size, V and V

- Recursively find MSTs T and T on V and V, respectively.

- Find an edge e of minimum weight connecting one vertex of V to one vertex of V

- Return the union of T and T and e.

True or False: This algorithm output a MST of G.

Hint: It is worth to consider the base case carefully

- True

- False