Prove that in a tree #leaves + #nodes of degree 2 $\geq \frac{n}{2}$

204 Views Asked by At

I am trying to solve the following problem:

Let $T = (V,E)$ be a Tree with $n = |V|$ nodes.

Let $b$ denote the number of leaves and $z$ the number of nodes with degree $2$.

I want to show that $$ b + z \geq \frac{n}{2}. $$

I want to use the Handshake lemma $$ \sum_{v \in V} \deg(v) = 2 | E | = 2(n-1), $$ but this hasn't brought me far.


EDIT

Using the suggestion from @Batominovski:

We know there are $n - b -z$ nodes with degree at least three. The handshake lemma thus gives: $$ b + 2z + 3(n - b - z) \leq \sum_{v \in V} \deg(v) = 2(n - 1) $$ Simplification yields $$ -2b - z + 3n \leq 2n - 2, $$ and further $$ n + 2 \leq 2b + z. $$ Finally $$ \frac{n}{2} + 1 \leq b + \frac{z}{2}. $$

1

There are 1 best solutions below

1
On BEST ANSWER

Hint: We have a stronger inequality $b+\dfrac{z}{2}\geq \dfrac{n}{2}+1$ if $n>1$ (where the equality holds if and only if the maximum degree of $T$ is at most $3$). Show that $$b+2z+3(n-b-z)\leq \sum\limits_{v\in V}\,\deg(v)\,.$$