Graph Theory Prove by Handshaking Lemma I have this question that I'm trying to prove by handshaking lemma. I'm having some difficulties trying to solve this problem. 
I believe in handshaking lemma you need to find the degree of vertices and edges and I think the number of vertices. I'm just not sure how to prove using the handshaking lemma without the information being directly mentioned.
Is there any tips or help I can get with this question? 
Bonus points if you can prove it with master theorem as well. =]
Question: "A complete 4-tree is a rooted tree in which each node has either 0 children or 4 children. Nodes with 0 children are called leaves and nodes with 4 children are called complete nodes. If L is the number of leaves and C is the number of complete nodes in a complete 4-tree, then L = 3C + 1."
 A: The handshaking lemma tells you that twice the number of edges is the sum of the vertex degrees, so we need to figure out the vertex degrees.  First, suppose there are no complete nodes.  Then the tree consists of a single leaf, and the theorem is true.  So we can assume the tree is rooted at a compete node.  The root has degree $4.$  Every other complete node has degree $5$ (a parent and $4$ children.)  A leaf has degree $1$.
$$ 2E = 4+5(C-1)+L\tag{1}$$
We need to count the edges another way.  In any tree with $N$ nodes, $E=N-1$, so $$E=C+L-1\tag{2}$$
Combine $(1)$ and $(2)$ to prove the theorem.
A: At first glance, I would try with induction over the number of vertices. The inductive step would go as follows. Assume $L =3C +1$, then try to add new vertices. Since it is a complete $4$-tree, we can only add exactly four children to a leaf at a time. Then the former leaf becomes a complete node ($L$ decreaces by one, $C$ increases by $1$), but then we also gain the four new leaves ($L$ increases by $4$). The net increments balance each other.
