Tree with no vertices of degree 2 has more leaves than non-leaves

Question

I wanted to try proving: if tree has no vertices of degree 2 it has more leaves than non leaves by strong induction. Here's my proof: For 1 vertex it's always true, 2 vertices also. Then let's prove that if for all trees with less than G's vertices it works, then it works for G. Remove arbitrarily edge from G. Then it will split G into two trees, $T_1$ and $T_2$, of which $l_1>n_1$, where $l_1$ is leaves and $n_1$ is non-leaves. Same applies for $T_2: l_2 > n_2$. If we were to join those trees and form G we have: $l_1+l_2>n_1+n_2$, since adding edge does not change the size of non-leaves and leaves in such sum. Thus we conclude that G is true for previous statement. Is this correct proof?

Answer 1

Unfortunately no, for more than one reason:

• After removing an edge, it's not guaranteed that $T_1$ and $T_2$ are graphs without vertices of degree $2$; so the induction hypothesis can't be invoked.
• Adding the edge back in can definitely alter the number of leaves and nonleaves (try some examples).