Graph theory, proving the existence of a vertex satisfying some conditions I am new to graph theory. I am reading this. I am having trouble understanding the following proof in the handout. Here's the statement and the proof which is from the link above.

Let $G$ be a tree and $v$ be any vertex of $G$. Let $v_1,v_2,...,v_t$ be the vertices adjacent to $v$. Let $e_i$ be the edge joining $v$ and $v_i$. Let $T_i$ be the subtree containing $v_i$ after removing edge $e_i$. (Draw a diagram for this. It will help.) Let $f(v)=max^{t}_{i=1}|V(T_i)|$.
Let's use a little intution here. Since $\sum |V(T_i)|=n-1$, if $f(v)$ is "large", then the tree looks unbalanced. If $f(v) \approx (n-1)/t$, then the tree looks balanced. We want to find vertex $v$ that minimizes $f(v)$, the vertex that makes the tree the most balanced.

Let $G$ be a tree with $n$ vertices and $\Delta > 1$ be the maximum degree
amongst all vertices in $G$. Using the same function $f$ as defined before, prove that there exists
a vertex $v$ such that
$$\frac{1}{\Delta}(n-1)\leq f(v)\leq \frac{\Delta-1}{\Delta} (n-1)$$
Left inequality follows for all $v$ from pigeonhole principle. To prove the right
inequality, choose $v$ such that $f(v)$ is minimum. Suppose $f(v) \ge (\Delta−1)/(\Delta)\cdot(n−1)+ 1$. Let $v_i$
be the neighbour of $v$ with $|T_i
| \ge (\Delta-1)/\Delta(n−1)+1$. Let $v = w_1, w_2, · · · , w_\Delta$ be the neighbours
of $v_i$. Then since the tree containing $v$ after removing $v_iv$ contains at most $1/\Delta(n - 1)$ vertices,
then $f(v_i) \leq (\Delta − 1)/\Delta(n - 1) - 1 < f(v)$, contradicting the minimality of $f(v)$. (Draw a
diagram to understand this proof better.)

I understood the proof of the left inequality. I don't really understand the proof of the right inequality. Can anyone elaborate? Thanks!
 A: The bound you're quoting is a bad bound. We can prove a better result: there is a vertex $v$ such that $f(v) \le \frac12 n$. This is easy to see once we draw the right diagram:

Suppose that $v$ has neighbors $v_1, v_2, \dots, v_k$. The subtrees $T_1, T_2, \dots, T_k$, which the text defines as

Let $T_i$ be the subtree containing $v_i$ after removing $e_i$, the edge joining $v$ and $v_i$

are simply the connected components of $T - v$. These are shown in red in the diagram above.
Claim. If $f(v) > \frac12 n$, then there is another vertex $v^*$ with $f(v^*) < f(v)$.
Proof. Suppose that $T_i$ is the largest of $T_1, T_2, \dots, T_k$, so that $f(v) = |V(T_i)|$. Then let $v^* = v_i$. Call $v^*$'s neighbors $v_1^*, v_2^*, \dots, v_m^*$, where $v_1^* = v$. Deleting $v^*$ leaves components $T_1^*, T_2^*, \dots, T_m^*$, which are shown in blue in the diagram above.
Since $T_2^*, \dots, T_m^*$ are all pieces of $T_i$, leaving out $v_i$ itself, we have $|V(T_j^*)| \le |V(T_i)|-1 < f(v)$ for $j=2, \dots, m$. Only $T_1^*$ can possibly be bigger than $T_i$.
What's more, $T_1^*$ and $T_i$ are the two connected components we get after deleting edge $v v_i$, so $|V(T_1^*)| = n - |V(T_i)| = n - f(v)$. If $f(v) > \frac12n$, then we conclude $|V(T_1^*)| < f(v)$ - and we've already proven that $|V(T_2^*)|, \dots, |V(T_m^*)| < f(v)$. Therefore $f(v^*) < f(v)$.

From the claim, it follows that if we pick the vertex $v$ that minimizes $f(v)$, we must have $f(v) \le \frac12n$.

It might seem like the bound $f(v) \le \frac{\Delta-1}{\Delta}(n-1)$ is better when $\Delta=2$, in which case it gives $\frac12(n-1) < \frac12n$. But in this case, then $\frac12(n-1)$ bound is false. Consider a path $P_n$, when $n$ is even. The best thing we can do is pick one of the two middle vertices, which will give $|V(T_1)| = \frac n2-1$ and $|V(T_2)| = \frac n2$. We'll get $f(v) = \frac12n$, not $\frac12(n-1)$.
(The flaw in the proof that gives $\frac{\Delta-1}{\Delta}(n-1)$ is the assumption that if $f(v) > \frac{\Delta-1}{\Delta}(n-1)$, then we must have $f(v) \ge \frac{\Delta-1}{\Delta}(n-1) + 1$. This is false when $\frac{\Delta-1}{\Delta}(n-1)$ is not an integer.)
