binary tree and one proof condition, why n should relate to three?

Question

I see this proof in binary tree on Question $1$. I see an example that tells a fact:

in a binary tree whit $n$ elements (n divisible by three) there is a node $u$ that number of nodes in a sub-tree with root $u$ at least $\frac{n}{3}$ and at most $\frac{2n}{3}$.

I couldn't get the point why this is true for every binary tree but this facts tell for $n$ divisible by three.

I need a simple and most simple proof like the one includes in mentioned link to get the idea and relation to divisibility by three.

Answer 1

Too long for comments....

Claim 1: For general binary trees, each vertex $y$ that is not a leaf has a child $y_1$ with size$(y_1)$ at least $\lfloor$size$(y)/2 \rfloor$; namely in general $y_1$ is the child of $y$ with the larger size. [If $y$ has 2 children with equal size then $y_1$ can be any child of $y$.]

This I trust you can see already.

1. This Claim 1 suffices to show that there is a separator w one edge $e$ where the smaller side has at least $n/3$ vertices if $n$ is divisible by 3. Indeed, let $y$ be a vertex, and then let $y_1$ be $y$'s child, where both (a) and (b) are satisfied: (a) size$(y_1) \ge$ $\lfloor($size$(y)/2 \rfloor$, and (b) size$(y) > 2n/3$ but size$(y_1) \le 2n/3$. [Note that such vertices exist, indeed march down the tree from the root at each step going to the vertex with the larger size; clearly there are $y$, $y_1$ so that (b) will be satisfied, by Claim 1 so will (a).] Then as $2n/3$ is an integer if $n$ divides 3, it follows that size$(y) \ge 2n/3+1$ and so Claim 1 implies that size$(y_1) \ge n/3$. So then $n/3 \le$ size$(y_1)$ as well, thus the string of inequalities $n/3 \le$ size$(y_1) \le 2n/3$ holds, and cutting the edge $e$ between $y$ and $y_1$ will leave size$(y_1)$ vertices on one side and $n-$size$(y_1)$ vertices on the other side.

2. This Claim 1 suffices also to show that there is a separator w one edge $e$ where the smaller side has at least $n/3$ vertices if $n$ is 2 mod 3. Indeed, let $y$ be a vertex, and then let $y_1$ be $y$'s child, where both (a) and (b) are satisfied: (a) size$(y_1) \ge$ $\lfloor($size$(y)/2 \rfloor$, and (b) size$(y_1) \le 2n/3$ but size$(y_1)> 2n/3$. Now, suppose size$(y_1) \le \lfloor \frac{n}{3} \rfloor$. Then by Claim 1, size$(y) \le 2$ size$(y_1)+1$. However, for $n$ that is 2 mod 3, the inequality $2\lfloor n/3 \rfloor +1$ $\le 2n/3$ holds. So this would imply that size$(y) \le 2n/3$ after all which is a contradiction. So it follows that size$(y_1)$ must be at least $\lfloor n/3 \rfloor +1$ $\ge n/3$, so it follows that $n/3 \le$ size$(y_1) \le 2n/3$. Finish as in Case 1.

Thus, the only case left is $n$ is 1 mod 3. And here there are some instances for which the best we can do is where the smaller side has $\lfloor n/3 \rfloor$ vertices, see the example given in your other question. If however we impose the additional condition that every interior vertex of $T$ with, the exception of exactly 1 vertex the root, has degree 3, then in fact a separator where the smaller side has at least ceiling of $n/3$ vertices even when $n$ is 1 mod 3. The proof in the link you provided establishes that.