MathOverflow is a question and answer site for professional mathematicians. 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

Suppose that there are $n$ vertices, we want to construct a regular graph with degree $p$, which, of course, is less than $n$. My question is how many possible such graphs can we get?

share|cite|improve this question
Why the "of course"? – Richard Kent Oct 10 '11 at 19:36
Because he defines "graph" as "simple graph", I am guessing. – Igor Rivin Oct 10 '11 at 19:38
This question appeared before on MO:… – Andy B Oct 11 '11 at 16:03
Thanks for your comment! – Youzhou Zhou Oct 11 '11 at 17:24
up vote 25 down vote accepted

McKay and Wormald conjectured that the number of simple $d$-regular graphs of order $n$ is asymptotically $$\sqrt 2 e^{1/4} (\lambda^\lambda(1-\lambda)^{1-\lambda})^{\binom n2}\binom{n-1}{d}^n,$$ where $\lambda=d/(n-1)$ and $d=d(n)$ is any integer function of $n$ with $1\le d\le n-2$ and $dn$ even.

Bender and Canfield, and independently Wormald, proved this for bounded $d$ in 1978, and Bollobás extended this to $d=O(\sqrt{\log n})$ in 1980.

McKay and Wormald proved the conjecture in 1990-1991 for $\min\{d,n-d\}=o(n^{1/2})$ [1], and $\min\{d,n-d\}>cn/\log n$ for constant $c>2/3$ [2]. These remain the best results.

The gap between these ranges remains unproved, though the computer says the conjecture is surely true there too. The formula apart from the $\sqrt2e^{1/4}$ has a simple combinatorial interpretation, and the universality of the constant $\sqrt2e^{1/4}$ is an enigma crying out for an explanation.

Incidentally this conjecture is for labelled regular graphs. For isomorphism classes, divide by $n!$ for $3\le d\le n-4$, since in that range almost all regular graphs have trivial automorphism groups (references on request). For $d=0,1,2,n-3,n-2,n-1$, this isn't true.

[1] Combinatorica, 11 (1991) 369-382.

[2] European J. Combin., 11 (1990) 565-580.

share|cite|improve this answer
Is there an asymptotic value for all d-regular graphs on n vertices (not necessarily simple)? – Amudhan Aug 23 '14 at 19:36
@Amudhan: The sparse case is here: . – Brendan McKay Aug 24 '14 at 2:33

There is no closed formula (that anyone knows of), but there are asymptotic results, due to Bollobas, see A probabilistic proof of an asymptotic formula for the number of labelled regular graphs (1980) by B Bollobás (European Journal of Combinatorics) or Random Graphs (by the selfsame Bollobas).

share|cite|improve this answer

Looking up OEIS, some related sequences are A005176 for the number of non-isomorphic regular graphs on $n$ vertices, and A005177 for the number non-isomorphic connected regular graphs on $n$ vertices.

share|cite|improve this answer

And 'of course', if you really want those graphs you might have a look at genreg by Markus Meringer:

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.