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."
Best Answer
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.