Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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

2 Answers 2

up vote 3 down vote accepted

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)\;.$$

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.