very hard proof on binary tree on number of child's I self study for preparing exam, and see a very difficult problem on question (2-b) on spring $2009$ at Here as attached follows.

I'm not need a very hard proof, just an intuitive step or idea about part (b). How we can deduce it?
 A: I would do parts (a) and (b) directly. We first note the following:

Claim 1: Let $y_i$ be any node in $T$ where size$(y_i) > 1$.
Then $y_i$ has a child $y_{i+1}$ where size$(y_{i+1})$ $\ge$ $\lfloor$size$(y_i)/2\rfloor$.

Indeed, as $T$ is binary, $y_i$ has at most 2 children, and at least 1 iff size$(y_i)>1$. If $y_i$ has exactly one child $y_{i+1}$ then size$(y_{i+1}) = $size$(y_i) -1 \ge \lfloor$size$(y_{i})/2\rfloor$ so Claim 1 is established for the case where $y_i$ has only one child. If $y_i$ has exactly 2 children $y^1_{i+1}$ and $y^2_{i+1}$
then size$(y^1_{i+1})$ $+$ size$(y^2_{i+1}) + 1$ $=$ size$(y_i)$. Assuming WLOG that size$(y^1_{i+1}) \ge $ size$(y^2_{i+1})$ it follows that
size$(y^1_{i+1}) \ge \lfloor$size$(y_{i})/2 \rfloor$ then, so set $y_{i+1}$ to be the vertex $y^1_{i+1}$. $\surd$
So we now show that there is a vertex $y$ such that $k \le$ size$(y) \le 2k$ for any positive integer $k<n$. Let $y_0$ be the root of the binary tree, and for each nonnegative integer $i$ set $y_{i+1}$ denote the child of $y_{i}$ of larger size. Then by Claim 1 $\lfloor$size$(y_i)/2\rfloor \le$ size$(y_{i+1})$ $<$ size$(y)$ because the tree is binary and $y-1$ has at most 2 children.
So let $l$ be the smallest integer such that size$(y_l) \le 2k$. If $l=0$ then $y_l=y_0$ the root of $T$ and size$(y_0)=n$ so $k \ge n/2$. If $k < n/2$ then $l$ is positive, and so size$(y_{l-1}) > 2k$ which implies by Claim 1 that size$(y_l) \ge k$ as well. Taking $y=\lfloor \frac{n}{2} \rfloor$ gives (b).

I think the exam writer wanted you to put $k=\lfloor n/3 \rfloor$ as in (a) and then take the edge between the node $v$ satisfying $k \le $ size$(v)  \le k$, and $v$'s parent.

We cannot always do any better $\lfloor \frac{n}{3} \rfloor$ for the smaller size w a separator that has only one edge. Let $T$ be a tree with 13 vertices: the vertices of $T$ are $v,w_1,w_2,w_3,w_4, y_1,y_2,y_3,y_4,u_1,u_2,u_3, u_4$, and the edges of $T$ are
$vw_1,vy_1, vu_1$, and then $w_1w_2, w_2w_3, w_3w_4, y_1y_2, y_2y_3, y_3y_4, u_1u_2, u_2u_3, u_3u_4$. So $T$ is a root $v$ where hanging off $v$ are 3 vertex-disjoint paths with 4 vertices each. Then every 1-edge separator of $T$ has a size with only at most $4 < 13/3$ vertices.
