Take the 2-minute tour ×
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.

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!

share|improve this question
add comment

2 Answers 2

up vote 5 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

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

share|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! –  RB14 Oct 10 '12 at 23:19
add comment

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|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. –  RB14 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
add comment

Your Answer

 
discard

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.