5

How many vertices of degree 1 are there in a tree with no vertices of degree more than 4? The only thing that I have right now is that the number of edges in a tree is n-1 where n is the number of vertices. Any help would be appreciated. Thanks in advance.

Marcus Pacheco
  • 71
  • 1
    There is an obvious lower bound, and a natural conjecture about the upper bound. You might want to include both in your question. – Did May 15 '13 at 22:20
  • 1
    Every tree has at least two leaves, and the path realizes this with no vertex of degree more than 2. My guess for the upper bound is that "higher branching means more leaves". Try working with a rooted tree with degree four at every non-leaf vertex. – Austin Mohr May 15 '13 at 22:24

2 Answers2

3

Let $k$ be the number of leafs in the tree. Let $n$ be the number of vertices.

It is known that $k \geq 2$ with equality for $T=P_n$.

As for the upper bound, the sum of degrees is at most $k+4(n-k)$. Thus

$$2(n-1)\leq k+4(n-k)=4n-3k \,$$

Solving this equality we get

$$k \leq \frac{2n+2}{3} \,.$$

Since $k$ is integer, we must have

$$k \leq \lfloor \frac{2n+2}{3} \rfloor \,.$$

The upper bound can be reached. Let $r$ be the remainder when $2n+2$ is divided by $3$. Then (as the above proof suggests) we need to construct a tree with $\lfloor \frac{2n+2}{3} \rfloor$ leafs, $r$ vertices of degree $2$ and $n-r- \lfloor \frac{2n+2}{3} \rfloor$ vertices of degree $4$. You can prove that such a tree exists by induction on $n$, the $P(n) \Rightarrow P(n+3)$ is easy (replace a leaf by a vertex of degree $4$ and connect it to 3 new leafs.)

N. S.
  • 132,525
1

If there are $n_i$ vertices of degree $i$, $1\le i\le 4$, then we must have $$n_1+2n_2+3n_3+4n_4=2(n-1)=2(n_1+n_2+n_3+n_4-1),$$ hence $$n_1=n_3+2n_4+2. $$ Especially, $$ 2\le n_1\le \frac{2n+2}3.$$ (The latter from $3n_1= 2(n_1+n3+n_4)+2-n_3\le 2n+2$).

Hagen von Eitzen
  • 374,180