Handshaking Tree

Nice problem...!!! Handshaking is a good title... Title remind me about the "HANDSHAKING LEMMA" , I have learnt before.

If it is 64 then it will be 8, but it is 65 and hence the value of k must be 9.

$\boxed{k=9}$

In a k-ary tree if internal nodes =n, then leaves = n (k-1)n+1. If nodes=8 leaves=8*(k-1)+1=65 and k=9

Let the root node have 9 children, two of them are leaf nodes (heaving no children) and the remaining 7 nodes have 9 children each (as leaf nodes of the tree and 7x9=63). therefore we have 65 leaf nodes and the tree is said to be 9-ary :)