I have the following homework (algorithms lecture):
Every $d$-ary tree $G=(V,E)$ contains a vertex $v$ such that the size of the subtree with root $v$ is at least $\frac{1}{d+1} \vert V \vert$ and at most $\frac{d}{d+1} \vert V \vert+1$
I have tried several proofs, but none of them seems legitimate for me. I would be glad if you have a valuable suggestion to prove this! Thank you in advance
Greetings from Germany (and sorry for my poor english!)
Edit: my current proof
To prove: A $d$-ary tree $G=(V,E)$ contains a vertex $v$ such that $\frac{1}{d+1} \vert V \vert \le \operatorname{tsize}(v) \le \frac{d}{d+1} \vert V \vert +1$.
Beforehand: The difference between the bounds is at least $d$ for any $d$ and for any $V$, since $ \frac{d}{d+1} \vert V \vert + 1 - \frac{1}{d+1} \vert V \vert \ge d \iff \frac{d}{d+1} \vert V \vert - \frac{1}{d+1} \vert V \vert \ge d-1 \iff \frac{d \vert V \vert - \vert V \vert}{d+1} \ge d-1 $ $ \iff \frac{(d-1)\vert V \vert}{d+1} \ge d-1 \iff \vert V \vert \ge d+1 $ Which is always fulfilled.
Consider the root of $G$. The size of the subtree of the root is clearly $\vert V \vert$. If we consider the child nodes of $r$ and obtain the node with maximum subtree size (call it $r'$), it will hold that the size of the subtree with root $r'$ lies in the interval $[\vert V \vert/d,\vert V \vert-d]$. The lower bound is the case when all direct subtrees of $r$ are equally sized, the upper bound the case when all other subtrees than $r'$ contain only a leaf.
From these facts we can derive that the tree size will diminish at least by $d$ if we choose the maximal subtree for each transition. We can also observe that the minimal bound always lies in the proposed intervall: $ \frac{1}{d+1} \vert V \vert \le \vert V \vert/d \le \frac{d}{d+1}\vert V \vert+1 $ From these two facts, it follows that we will find a vertex $v$ satisfying the above property. $\square$