Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.


share|cite|improve this question
up vote 6 down vote accepted

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


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.

share|cite|improve this answer
Hi, thanks for your answer. that's look now very simple, I've thinking about this for hours, tried to approach from many ways. And yes, I need to show how to build such a tree but with your help I'll try to do it myself :) Thanks! – rboy Oct 10 '12 at 23:19

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$.

share|cite|improve this answer
Thanks for your answer. I didn't study Prüfer code, but I did study Cayley's formula, if it has something to do with it. – rboy Oct 10 '12 at 23:22
Yes, it has a lot to do with it :-) look at the wikipedia link. – Dennis Gulko Oct 10 '12 at 23:44

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.