Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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

I have a hard time to find a way to construct a k-regular graph out of n vertices. There seems to be a lot of theoretical material on regular graphs on the internet but I can't seem to extract construction rules for regular graphs.

My preconditions are

k<n and (n%2 == 0 or k%2 == 0)

Is an adjacency matrix the way to go here? If so, how would I use it?

Is this even a mathematical problem?

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

If $k=2m$ is even, put all the vertices around a circle, and join each to its $m$ nearest neighbors on either side.

If $k=2m+1$ is odd, and $n$ is even, put the vertices on a circle, join each to its $m$ nearest neighbors on each side, and also to the vertex directly opposite.

share|cite|improve this answer
Note that for $k \gt 1$ the resulting $k$-regular graph is connected, because it contains the $n$-cycle solution given by $k=2$. – hardmath May 21 '12 at 3:29

Once you have an initial $k$-regular graph, you can generate many more by randomly applying the following simple switching operation:

Switching operation illustration

provided it does not introduce a parallel edge or loop.

share|cite|improve this answer

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.