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!
$\endgroup$ 02 Answers
$\begingroup$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.
$\endgroup$ 1 $\begingroup$Assuming you mean labeled vertices (since all $k$-regular trees are isomorphic, so if you don't label the vertices there will be just one). Did you study the Prüfer code? If yes, then you should know that counting those trees is the same as counting words of length $n-2$, constructed from $n$ such that every letter that appears in the word - appears exactly $k-1$ times. Hence there exists a $k$-regular tree on $n$ vertices if and only if $k-1$ divides $n-2$.
$\endgroup$ 2
