# Why for number of leaves in a tree (all types of trees) is it true

I have to prove the following claim, given the tree $T=(V,E)$, $|V|\geq3$: $$|V_1| \leq \frac { |V| \times (\Delta (V) - 2) + 2 }{ \Delta (V) - 1 }$$ where $|V_1| -$ number of leaves in a tree, and $\Delta (V) -$ maximum degree of all vertices.

I was sitting on this question for days and have no idea how to prove it.

Can someone help?

Thanks!

-
What about induction on $|V|$? Assume $|V|=n+1$ then delete a leaf.. –  Berci Sep 28 '12 at 7:59
@Berci Do you think that induction is correctly solution? I do not understand where may appear a fraction.. –  jofisher Sep 28 '12 at 8:14

Let $V_2=V\setminus V_1$, the set of interior vertices of the tree, and to simplify notation write $\Delta$ for $\Delta(V)$. The inequality can be rearranged to yield

$$(\Delta-2)|V|+2\ge(\Delta-1)|V_1|=(\Delta-2)|V_1|+|V_1|$$ and then

$$|V_1|\le(\Delta-2)(|V|-|V_1|)+2=(\Delta-2)|V_2|+2\;.\tag{1}$$

I’ll prove $(1)$ by induction on $|V|$.

Pick two leaves, $v_0$ and $v_n$, and let $v_0v_1\dots v_n$ be the unique path between them, which I’ll call the spine of the tree. Each of the vertices $v_1,\dots,v_{n-1}$ has degree at most $\Delta$, so it’s an end of at most $\Delta-2$ edges that aren’t in the spine. For each non-spine edge $e$ incident at $v_k$ let $T_k(e)$ be the subtree whose vertices are $v_k$ and all vertices of $T$ whose unique path to $v_k$ included the edge $e$. Let the vertex set of $T_k(e)$ be $V_k(e)$, and let $V_{k,1}(e)$ and $V_{k,2}(e)$ be the sets of leaves and interior vertices, respectively. Finally, let $t_k=\deg(v_k)-2$ be the number of subtrees incident at $v_k$; clearly $t_k\le\Delta-2$.

By the induction hypothesis we have

$$|V_{k,1}(e)|\le(\Delta-2)|V_{k,2}(e)|+2$$

for each of these subtrees.

Each $v_k$ is a leaf of each $T_k(e)$, so

\begin{align*} |V_1|-2+\sum_kt_k&=\sum_{k,e}|V_{k,1}|\\ &\le\sum_{k,e}\left((\Delta-2)|V_{k,2}(e)|+2\right)\\ &=(\Delta-2)\sum_{k,e}|V_{k,2}(e)|+\sum_{k,e}2\\ &=(\Delta-2)\Big(|V_2|-(n-1)\Big)+2\sum_kt_k\;, \end{align*}

and therefore

\begin{align*} |V_1|&\le 2+(\Delta-2)|V_2|-(n-1)(\Delta-2)+\sum_kt_k\\ &\le 2+(\Delta-2)|V_2|\;, \end{align*}

since $$\sum_kt_k\le(n-1)(\Delta-2)\;.$$

-

$$2 = 2|V| - 2 |E| = \sum_{v \in V} 2 - \deg(v) \geq |V_1| + (2 - \Delta(V))(|V| - |V_1|).$$

Rearranging as in Brian M. Scott's answer gives the required result.

-