Question on trees and leaves

Question

Let $T$ be a tree and $S$ the set of vertices in $T$ with degree at least 3. Prove that the number of leaves in $T$ is: $$2+\sum\limits_{v\in S} (deg(v)-2).$$ I ran into this example in my text and it said it should be an easy exercise to prove. But I'm not sure I can even see it being true. Any insight and a proof would be welcome.

Answer 1

Since every non-leaf outside $S$ has degree $2$, the question asks to prove that in a tree the number of leaves equals $2+\sum (\deg v - 2)$ where the sum is over all non-leaves. Let $l$ be the number of leaves and let $n$ be the total number of vertices. Then there are $n-1$ edges, hence $2(n-1) = \sum \deg v$ where the sum is over all vertices (in a graph the sum of the degrees of the vertices equals twice the number of edges, as pointed out in the comments). Notice that this implies that $2(n-1) = l + \sum \deg v = l + 2(n-l) + \sum (\deg v - 2)$ where the sum is over all non-leaves, of which there are $n-l$. Rearranging gives the desired conclusion.

Alternatively, one can proceed by induction on the number of vertices. Delete some leaf $v$ of $T$. Let $w$ be the neighbour of $v$. If $w$ is a leaf in $T-v$ then $T$ and $T-v$ have the same number of leaves and the claim follows. If $w$ is not a leaf in $T-v$ then $T$ has a leaf more than $T-v$, but the sum $2+\sum(\deg v - 2)$ is $1$ larger as well since the vertex $w$ has a new neighbour.

Answer 2

More for understanding than a rigourous proof:

You can see the tree as a stem with several branches. The stem has two leaves, one in each end, and each branch adds one leaf. The branching points are precisely the vertices with degree at least 3, and they add $\deg(v)-2$ branches, so the formula is clearly correct.