Case when there are more leaves than non leaves in the tree Prove that there are more leaves than non-leaves in the graph that don't have vertices of degree 2.
Ideas: If graph doesn't have vertices of degree 2 this means that vertices of the graph have degree 1 or $\geq$ 3. Vertices with degree 1 are leaves and vertices with degree $\geq$ 3 are non-leaves. Particularly, root has degree 3 (therefore 3 vertices on the level 1), level 2 has 6 vertices, level $i$ has $3*2^{i-1}$ vertices. 
Let's assume there are $n$ level, therefore according to assumption $1+\sum_{i=1}^{n-1} 3*2^{i-1} < 3*2^{n-1}$. 
There are few problems: currently I don't have an idea how to show that the above inequality is true. In addition, do I need to consider particular cases when no all leaves on the same level of the tree, or maybe when no all non leaves have the same degree, however intuitively all these cases just extend number of leaves.
I will appreciate any idea or hint how to show that the assumption is right.
 A: If $D_k$ is the number of vertices of degree $k$ then $\sum k \cdot D_k=2E$ where $E$ is the number of edges. In a tree, $E=V-1$ with $V$ the number of vertices. So if $D_2=0$ you have
$$1D_1+3D_3+4D_4+...=2E=2V-2\\ =2(D_1+D_3+D_4+...)-2.$$
From this,
$$2D_1-2-D_1=(3D_3+4D_4+...)-(2D_3+2D_4+...),$$
$$D_1-2=1D_3+2D_4+3D_5+...,$$ and then
$$D_1>D_3+2D_4+3D_5+... \ge D_3+D_4+D_5+...$$
The sum $D_3+D_4+D_5+...$ on the right here is the number of non leaves, since $D_2=0$, while $D_1$ is the number of leaves, showing more leaves than non leaves.
A: Once you know that all non-empty trees have leaves, you can use induction on the number of vertices.
The tree with one vertex being a leaf, the base case checks. For a tree $T$ with $n>1$ vertices, choose a leaf, remove it, and if its neighbour had degree $3$, which now becomes $2$, also remove that neighbour while combining the remaining two edges into a single edge. The absence of multiple edges in $T$ ensures that this combination gives a valid edge, and the absence of loops ensures that the combined edge is not a multiple one nor occurs in a loop; we have reduced to a tree $R$, and no remaining vertices have degree $2$. So the property holds by assumption for $R$, and $T$ either has just one more leaf than $R$ (if no second vertex was removed) or one more leaf and one more non-leaf vertex than $R$; in either case the property for $T$ follows.
