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.

  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?
  • $\begingroup$ I didn't quite get how you derived your formulas in your second statement. $\endgroup$ – user72151 Oct 17 '15 at 21:43
  • $\begingroup$ The sum of the degrees is twice the number of edges. Since each tree with $n$ vertices has $n-1$ edges, the average degree is $\frac{\sum \textrm{deg}(v)}{n} = \frac{2(n-1)}{n}$. $\endgroup$ – Michael Biro Oct 17 '15 at 21:45
  • $\begingroup$ Okay, got this one. What about the second inequality? And I assume for $l$ you mean leaves, not trees. $\endgroup$ – user72151 Oct 17 '15 at 21:51
  • $\begingroup$ Yes, thanks, $l$ leaves. Just look at $\sum \textrm{deg}(v)$ in a different way - each leaf contributes $1$ to the sum, and there are $l$ of them. Each internal vertex contributes at least $3$ and there are $i$ of them. Therefore, $\sum \textrm{deg}(v) = 2(n-1) \geq 3i + l$. $\endgroup$ – Michael Biro Oct 17 '15 at 21:56
  • 2
    $\begingroup$ Since $i + l = n$, all you need to show is that $l \geq \frac{n}{2}$. $\endgroup$ – Michael Biro Oct 17 '15 at 22:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy