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



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