Fewer degree-$3+$ nodes than leaf nodes in a tree

Question

Considering this question, I was struck by the idea that:

For a graph $G$ that is a tree, the number of degree-$1$ nodes exceeds the number of nodes of degree $3$ or higher.

.. which would fairly directly solve that question.

The intuition is as follows: each degree-$3$ node adds a branch to the tree, which must also add a degree-$1$ node. Higher degree nodes add branches per extra degree. This intuition adds a numerical prediction: $$ \sum_{k\in H}(d(k)-2) = |L|-2$$ where $H$ is the set of vertices in $G$ with degree $3$ or higher and $L$ is the set of degree-$1$ nodes, with two leaf nodes being allocated to a simple unbranched tree.

Can anyone produce or reference a more formal proof?

Answer 1

A tree on $n$ vertices has $n-1$ edges. So if there are $a$ leaves and $b$ vertices of degree at least three, then by the handshaking lemma, $$a+2(n-a-b)+3b\leq\sum \deg v=2(n-1)\implies a\geq b+2.$$

Answer 2

Let $n_d$ be the number of nodes of degree $d$. By the handshaking lemma and the fact that a tree on $n$ nodes has $n-1$ edges, we have $$\sum_d d n_d = 2\left(\sum_d n_d - 1\right),$$ which implies that $$-2 = \sum_d (d-2) n_d = -n_1 + \sum_{d \ge 3} (d-2) n_d.$$

Answer 3

You could prove it also with induction on the number $n\geq 2$ of vertices. Let $\ell$ be the number of leafs and $t$ the number of degree 3 or more vertices.

If $n=2$ then $\ell=2$ and $t=0$ so $\ell>t$.

Induction step: In a tree $T$ there is a leaf $m$ with neigbour $w$. If we remove it we get smaller $T'$ tree, so by induction hypothesis we have $\ell'>t'$ in $T'$. Now give $m$ back, then:

• $\ell= \ell'$ if $w$ is leaf in $T'$, but then $t=t'$ so $\ell>t$;
• $\ell=\ell'+1$ if $w$ is not leaf in $T'$, but then we have two subcases:
  • If $d(w) = 2$ then $t=t'+1$ so $\ell >t$
  • If $d(w) > 2$ then $t=t'$ so $\ell >t$ again.