4
$\begingroup$

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!

  • 0
    @Berci Do you think that induction is correctly solution? I do not understand where may appear a fraction..2012-09-28

2 Answers 2

4

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 = 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.