Partition a binary tree by removing a single edge

The question is :

B-3 Bisecting trees 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| \leq \frac{3n}{4}$ and $|B| \leq \frac{3n}{4}$, by removing a single edge.

The proof I came up with is using induction on the number of nodes.

Assume that we can partition a tree with (n - 1) nodes in way that fulfills the requirement. To prove we can also do it on a n nodes tree G, first remove a leaf node v from the tree and partition it, which result in 2 binary tree A' and B', which has property

$$ \frac{(n-1)}4 \leq |A'|, |B'| \leq \frac{3(n-1)}4 $$

Without loss generality, we assume that v's parent is in A'. We put v back to A', got 2 tree, A'' and B''. If and A'' still B'' fulfill the requirement for n, then we get the partition we need.

On the other, if adding back v breaks the requirement, it means

$$ \frac{3n}4 \lt |A''| = |A'| + 1 \leq \frac{3n + 1}4 $$

Since A'' is a binary tree with less than n nodes, we can find a partition A''', B''' of A'', which has the property

$$ |A'''| \leq \frac{3}4 |A''| \leq \frac{9n + 3}{16} \leq \frac{3n}4 $$

Without loss generality, we can assume $|A'''| \geq |B'''|$, which means

$$ |A'''| \geq \frac{|A''|}2 \gt \frac{3n}{8} \gt \frac{n}4 $$

Therefore, A''' and G - A''' is a partition for G which fulfills the requirement.

Edit : proof of the base case.

For $ n = 1 $, the proposition doesn't apply as there no way to partition it to 2 nonempty set.

For $ n = 2 $, there's only 1 edge in the tree. By removing this edge, we get 2 sets, A, and B which are

$$ 2 * \frac1{4} = \frac1{2} \lt |A|, |B| \lt 2 * \frac3{4} = \frac3{2} $$

So A and B is a eligible partition. The proposition holds for base case $ n = 2 $.

Is my proof correct? Any simpler proof exist?

(I Google a while but didn't find any solution for the question, so I guess it might be useful to write down my proof as it might be useful for other people.)

Solution 1:

The standard proof is algorithmic. Root your tree arbitrarily, and execute the following algorithm. Start with the root $r$. Define a sequence $v_0 = r,v_1,\ldots$ as follows: for each $i$, $v_{i+1}$ is the child of $v_i$ with the larger subtree size (break ties arbitrarily). The sequence ends at some leaf $v_N$.

Denote by $T(v_i)$ the size of the subtree rooted at $v_i$. Since $T(v_0) = n$ and $T(v_N) = 1$, there must be some first $i$ such that $T(v_i) \geq (3/4)n$ and $T(v_{i+1}) < (3/4)n$. If $v_{i+1}$ is the only child of $v_i$ then $T(v_i) = (3/4)n$, and so disconnecting $v_i$ from its ancestor, we're done.

Otherwise, let $w$ be the other child of $v_i$. Since $T(v_i) \geq T(w)$, we have $$(3/4)n \leq T(v_i) = 1 + T(v_{i+1}) + T(w) \leq 1 + 2T(v_{i+1}).$$ Therefore for $n \geq 4$, $$n/4 \leq (3n-4)/8 \leq T(v_{i+1}) < (3/4)n,$$ and so disconnecting $v_{i+1}$ from $v_i$, we're done. If $n < 4$ then a case-analysis suffices.