a $k$-regular tree is a tree for which all vertices have a degree of $k$ or $1$ (internal veritces have a degree of $k$ and the leaves have a degree of $1$).
I've been asked to find for which values of $n$ there exists a $k$-regular trees on $n$ vertices.
I can prove that a $k$-regular graph on $n$ vertices exists if $n$ is even, or $k$ is even, but not if both are odd. but I'm having hard times finding a sufficient and necessary condition for an existence of $k$-regular tree.
I'm looking for the most simple proof, using the most basic theorems as possible.
Thank!
Best Answer
If the tree has $m$ vertices of degree $k$ and $n-m$ vertices of degree $1$, then by the Handshakking lemma
$$km+(n-m) =\sum \mbox{degree} = 2 \mbox{ no edges} = 2n-2 $$
This proves that
$$(k-1)m=n-2$$
thus $k-1$ must divide $n-2$.
You also need to prove that if this is the case, it is possible to build such a tree....But this is easy.