Let G be a tree having n n vertices. Suppose that every vertex in G which is not a leaf has degree k, where k > 1 . Find a formula, in terms of n and k , for the number of leaves of G.
I started drawing this out so that I can try visualizing it. I realized that the first " level" of G will have k leaves. i.e when k=2, the most basic tree will have 2 leaves( this graph will have 2 leaves no matter it's size when k=2). when K=3, the most basic tree will have 3 leaves, then it will have 4, then 5, then 6 as you grow the tree. when K=4 it will start at 4 leaves then go to 6 then 8…
I see the pattern but cannot relate it back in terms of n and k.
Best Answer
Let $V_k$ be the set of vertices in the graph $G$ with degree $k$. Then, by the hand-shaking lemma, $$2|E(G)|=\sum_{m=o}^{\infty}|V_m|*m=|L|+k(n-|L|)$$ Here $L$ denotes the set of leaves. As $|E(G)|=n-1$ is a characterization of a tree, we have $$2|E(G)| = 2n-2=|L|+k(n-|L|)=|L|+kn-k|L| \Rightarrow |L|=\frac{2n-2-kn}{1-k}$$