Find the bounds of the number of leaves in a tree

357 Views Asked by At

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:

  1. $m \geq ( n + 2 ) / 2$
  2. $( n + 4 ) / 3 \leq m \leq ( n + 2 ) / 2$
  3. $1 \leq m \leq ( n + 4 ) / 3$
  4. $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.

2

There are 2 best solutions below

2
On

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

0
On

$m\geq\frac{(n+2)}{2}$ because as you said, $m.1+0.2+n_3.3+n_4.4+....=2(n-1)$. Therefore, $2(n-1)\geq m+3(n-m)$, if we consider all other nodes to be of degree$\geq 3$. Solving this, we get the first option.