Problem: Let $n ≥ 3$ be an integer, $T$ be tree on $n$ vertices, with no vertex of degree $2$, and m be the number of leaves in $T$. It is true that we always have one of the following:
- $m \geq ( n + 2 ) / 2$
- $( n + 4 ) / 3 \leq m \leq ( n + 2 ) / 2$
- $1 \leq m \leq ( n + 4 ) / 3$
- $m = ( n + 4 ) / 3$
My question: I know that for every graph $2 | E | = \sum _ { v \in V } d ( v )$. More specifically we have for a tree $2(n-1) = \sum _ { v \in V } d ( v )$. Now since there are no vertices of degree $2$ and I know we have $m$ vertices of degree 1:
$$m\cdot 1 + 0\cdot 2+ n_3\cdot 3+n_4\cdot 4+\ldots=2(n-1)$$ with $n_k$ the number of vertices of degree $k$. Clearly we have an upper bound quiet generous: $$m\leq 2(n-1)$$
I can't seem to find another way to bound the value of m.
$m$ could not be greater than $n$ as the number of nodes is $n$. The upper bound for $m$ is $n-1$ (as an example a star). Hence, $m \leq n-1$.