Many divide-and-conquer algorithms that operate on graphs require that the graph be bisected into two nearly equal-sized subgraphs, which are induced by a partition of the vertices. This problem investigates bisections of trees formed by removing a small number of edges. We require that whenever two vertices end up in the same subtree after removing edges, then they must be in the same partition.

a. Show that we can partition the vertices of any n-vertex binary tree into two sets A and B, such that |A| ≤ 3n/4 and |B| ≤ 3n/4, by removing a single edge.

b. Show that the constant 3/4 in part (a) is optimal in the worst case by giving an example of a simple binary tree whose most evenly balanced partition upon removal of a single edge has |A| = 3n/4.

c. Show that by removing at most O(lg n) edges, we can partition the vertices of any n-vertex binary tree into two sets A and B such that |A| = ⌊n/2⌋ and |B| = ⌈n/2⌋.