◀ ▲ ▶Branches / Graph-theory / Proof: By Induction

Proof: By Induction

(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$
    ∎

Thank you to the contributors under CC BY-SA 4.0!

Github:

References

Bibliography

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