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:

Proofs: 1

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




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