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

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?

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

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

• And there's the numerical result. Thanks. Feb 8, 2021 at 21:51

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.