Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$

share|improve this question
    
a) There's a $-1$ missing on the right-hand side of one of the inequalities in the long equivalence chain. b) It's not true that $|V|\ge d+1$ is always fulfilled; e.g. you might only have the root. You'd need to argue that if $|V|\lt d+1$, the condition requires a subtree of size $1$, which always exists. c) You seem to be assuming a full $d$-ary tree; a general $d$-ary tree need not have vertices on all branches of a non-leaf. –  joriki Nov 5 '12 at 5:54
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.