◀ ▲ ▶Branches / Graph-theory / Lemma: Relationship between Tree Degree, Tree Height and the Number of Leaves in a Tree

Lemma: Relationship between Tree Degree, Tree Height and the Number of Leaves in a Tree

Let $T(V,E)$ be 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$. Then the following inequalities hold:

• $l\le d^h$
• $|V|\le 2\cdot d^h$
• $h\ge\log_d(l).$

Table of Contents

Proofs: 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