(related to Lemma: Relationship between Tree Degree, Tree Height and the Number of Leaves in a Tree)

- By hypothesis, $T(V,E)$ is a tree with $|V|$ vertices and a given root $r$.
- Let $h$ be the height of $T$ with respect to $r$, let $d$ be the degree of $T$ with respect to $r$, and let $l$ denote the number of leaves in $T$.
- We prove the inequalities by induction on the height $h.$
- Base case $h=0$:
- If the height of the tree is $0$ then $|V|=1=l\le d^0\le 2\cdot d^0.$
- Moreover, $0\le \log_d(l)$ (logarithm to the base of the tree degree $d$).

- Induction step $h\to h+1$
- Assume, for all trees $T^\prime$ with heights $h^\prime\le h$ we have the inequalities * $l^\prime\le d^{h^\prime}$ * $|V|\le 2\cdot d^{h^\prime}$ * $h^\prime\ge\log_d({l^\prime}).$
- Let $T(V,E)$ be a tree of height $h+1$.
- We prove $l+1\le d^{h+1}$: * Note that the leaves at the altitude $h+1$ of a tree $T$ have leaves of $T^\prime$ as their predecessors. * Since $T$ is of degree $d,$ each leaf of $T^\prime$ can have at most $d$ new successors (leaves) in $T.$ * It follows $l+1\le d\cdot d^{h}=d^{h+1}.$
- We prove $|V|\le 2\cdot d^{h+1}$ * We have just shown that at most $d^{h+1}$ new vertices in $T$ can be added at the altitude $h+1$. * The overall number of vertices in $T$ can be, therefore, estimated as $|V|\le 2d^h+d^{h+1}\le d^{h+1}+d^{h+1}=2d^{h+1}.$
- We prove $h+1\ge\log_d({l+1})$:
* Since $l+1\le d^{h+1}$, it follows $\log_d(l+1)\le h+1$∎

**Erk, Katrin; Priese, Lutz**: "Theoretische Informatik", Springer Verlag, 2000, 2nd Edition