Proving the number of leaves is larger by at least two than the number of vertices with a degree of at least 3

Question

Prove that in every tree, the number of leaves is larger by at least two than the number of vertices with a degree of at least 3.

Trying induction, I get something that is too short to be right, and I don't see how to use $\sum d(v)=2(n-1)$ because we have to prove here that $\displaystyle\sum_{d(v)=1}1 \ge \sum_{d(v)\ge 3}1+2 $ and there's no accounting here for the $d(v)=2$.

Another thing I noticed is that every vertex in a tree such that $d(v) > 1$ leads to an amount $> 1$ of leaves. So for every single $d(v)=3$ there will be at least two leaves. But can I prove that? any hints?

Answer 1

Denoting the # of vertices with degree $i$ as $X_i$, we have $$ \sum_{i=1}^k i\cdot X_i = 2(n-1) \tag{1} $$ where $k$ is the largest degree.

Moreover, we also have $$ \sum_{i=1}^k X_i = n \tag{2} $$

Thus, computing $2 \cdot (2)-(1)$ leads to \begin{align} &X_1 + \sum_{i=3}^k (2-i)\cdot X_i = 2 \\ \Rightarrow &X_1 = \sum_{i=3}^k (i-2)\cdot X_i + 2 \geq \sum_{i=3}^k X_i + 2 \end{align}

Remind that $X_1$ is the # of leaves. We thus have proved the argument.

Answer 2

HINT: Suppose that $v$ is a vertex of degree $2$ connected to vertices $u$ and $w$; if you remove $v$ and join $u$ and $w$ by an edge, you don’t change the degree of any of the remaining vertices, and you still have a tree. Repeat this process until you have no vertices of degree $2$. Now let $\ell$ be the number of leaves and express $\sum_v\deg v$ for the reduced tree in two different ways.

Answer 3

Induction is the way, but in a more simple way:

If you remove a leaf from the tree, it is still a tree, and you have three cases

1 - the father of the leaf you removed is now a leaf, so the number of leaves and nodes with degree $\ge$3 are both the same

2 - the father of the leaf you removed had exactly degree 3, so now it has degree 2, and the number of leaves and nodes with degree $\ge$3 both decreased by one

3 - the father of the leaf you removed had degree $ >$3, so now it has degree $\ge$3, and the number of leaves has decreased by one, and nodes with degree $\ge$3 remained the same

In each case, the induction works