# Maximum Leaves

Printable View

• February 7th 2011, 10:26 AM
meggnog
Maximum Leaves
For $\Delta \geq 3$ , consider all trees where each vertex has degree $\Delta$ or less, and where the longest path is of length k or less. Show that the maximum number $l_{max}$ of leaves among such trees satisfies the following:

$l_{max} \leq \Delta (\Delta - 1)^{k/2-1}$