In this problem, we consider a decomposition of a binary tree that may be useful when using a divide-and-conquer approach to solve some problem on that tree. (a) Show that for any binary tree with n vertices, there is an edge such that removing it partitions the tree into two subtrees each with at most 3n/4 vertices. (b) Show that the constant in (a) is optimal in the sense that it results in the most balanced partition. More precisely, show that there are arbitrarily large trees for which the best partition factor is 3/4 (it is not sufficient to display a single tree of some size). (c) Show that given any tree with n vertices, by removing O(lg n) edges, we can partition the tree into two forests (collections of trees) A and B with numbers of vertices n/2 and n/2