3. A balanced bipartition of set X splits X into two parts A and B so that the sizes of A and B differ by at most 1. In particular, when X is even, A=B=X/2; when X is odd, A=B1=X/2. We refer to the bipartition as AB. For example, {b,e}{a,c,d} and {a,c}{b,d,e} are two different balanced bipartitions of {a,b,c,d,e}. On the other hand, we treat {a,b}{c,d} and {c,d}{a,b} as the same bipartition of {a,b,c,d}. (a) (2 pts) Determine the number of balanced bipartitions of X for X=6 and X=7 (b) (8 pts). Let us now use balanced bipartitions for computing minimum spanning trees. Suppose G=(V,E) is a connected undirected graph with nonnegative edge weights. If V1V2 is a balanced bipartition of V, let E1 be the set of edges that are incident only to vertices in V1,E2 be the set of edges 1 that are incident only to vertices in V2, and E12 be the set of edges connecting a vertex in V1 to one in V2. Consider the following algorithm: Choose a balanced bipartition V1V2 of V so that a minimum weight edge of G is in E12. Recursively solve the minimum-spanning-tree problem on each of the two subgraphs G1=(V1,E1) and G2=(V2,E2). Finally use the minimum-weight edge in E12 to connect the two minimum spanning trees into a single spanning tree. Either argue that the algorithm correctly computes a minimum spanning tree of G, or provide an example on which the algorithm fails. (There is no need to analyze its running time)