If a tree has 5 vertices of degree 2, 3 vertices of degree 3, 4 vertices of degree 4, then how many leaves are there in that tree?
I know the tree has at least 12 vertices and so it must have at least 11 edges. Also the number of leaves must be odd but I could not proceed further.
Best Answer
If $k$ is the number of leaves then the total number of vertices in the tree is $12+k$ with $11+k$ edges and the sum of the degrees is $\sum\deg(v)=(5\times 2)+(3\times 3)+(4\times 4)+(k\times 1)=35+k$. Now by handshaking lemma, $$35+k=2(11+k)\Rightarrow k=13.$$