Tree having no vertex of degree 2 has more leaves than internal nodes

Question

If $T$ is a tree having no vertex of degree 2, then $T$ has more leaves than internal nodes. Prove this claim by a) induction, b) by considering the average degree and using the handshaking lemma.

I know that if a tree $T$ has two or more vertices, meaning $|V(T)| \geqslant 2$, then $T$ has at least two leaves. I also know that according to the handshaking lemma the sum of degrees of each vertex is equal twice the number of edges in a graph, meaning $\sum_{v \in V} d(v) = 2|E|$.

I also think that the claim is true, while if there is no vertex having degree 2, it means that all the vertexes have degree either $0 \geqslant d(v) \geqslant 1$ (trivial cases), or $d(v) \geqslant 3$, where we will have more leaves than nodes.

Answer 1

1. For a proof by induction, take such a tree and split it at an internal vertex. If the internal vertex has degree $k$, you get $k$ pieces, each with no internal vertex of degree 2. Use the inductive hypothesis to complete the argument.
2. The average degree of a tree is $\frac{2(n-1)}{n}$. If the tree has $i$ internal vertices and $l$ leaves, you get that $3i + l \leq 2(n-1)$. Can you finish the argument?

Answer 2

Consider any tree $T$ on $n$ vertices with no vertex of degree two. Let there be $k$ leaves and $n-k$ non-leaves. Since every non-leaf vertex has at least degree three, we have $$ \begin{aligned} 2|E(G)| & =\sum_x \text { is a leaf } \operatorname{deg}(x)+\sum_x \text { is a non-leaf } \operatorname{deg}(x) \\ & \geq k+3(n-k) \\ & =3 n-2 k \end{aligned} $$

Since $|E(G)|=n-1$, we thus have $2 n-2 \geq 3 n-2 k$, which after rearrangement yields $k \geq n-k+2$ and therefore, $k \geq n-k$. This is exactly what we need.

Answer 3

All you need to know about a tree is that it has no isolated vertices (leaving aside the tree of order $1$ as a special case), and that it has fewer edges than vertices. Hence the degree-sum, being twice the number of edges, is less than twice the number of vertices, whence the average degree is less than $2$.

Since the average degree is less than $2$, and there are no vertices of degree $0$, there must be more vertices of degree $1$ (leaves) than vertices of degree at least $3$. If there are no vertices of degree $2$, then every internal vertex has degree at least $3$, so there are more leaves than internal vertices.