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

graph theorytrees

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.

Best Answer

  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?
Related Question