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?



How many $p$-regular graphs with $n$ vertices are there?
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. <http://cs.anu.edu.au/~bdm/papers/nickcount.pdf>


[2] European J. Combin., 11 (1990) 565-580. <http://cs.anu.edu.au/~bdm/papers/highdeg.pdf>


ADDED in 2018: The "gap between those ranges" mentioned above was filled by Anita Liebenau and Nick Wormald [3]. Another proof, by Mikhail Isaev and myself, is not ready for distribution yet.


[3] <https://arxiv.org/abs/1702.08373>


