# Random regular graph

A random r-regular graph is a graph selected from $\mathcal{G}_{n,r}$, which denotes the probability space of all r-regular graphs on n vertices, where 3 ≤ r < n and nr is even.[1] It is therefore a particular kind of random graph, but the regularity restriction significantly alters the properties that will hold, since most graphs are not regular.

## Properties of random regular graphs

As with more general random graphs, it is possible to prove that certain properties of random r-regular graphs hold almost surely. In particular, for $r \ge 3$, a random r-regular graph of large size is almost surely r-connected.[2] In other words, although r-regular graphs with connectivity less than r exist, the probability of selecting such a graph tends to 0 as n increases.

If $\epsilon$ > 0 is a positive constant, and d is the least integer satisfying

$(r-1)^{d-1} \ge (2 + \epsilon)rn \ln n$

then, almost surely, a random r-regular graph has diameter at most d. There is also a (more complex) lower bound on the diameter of r-regular graphs, so that almost all r-regular graphs (of the same size) have almost the same diameter.[3]

The distribution of the number of short cycles is also known: for fixed m ≥ 3, let Y3,Y4,…,Ym be the number of cycles of lengths up to m. Then the Yi are asymptotically independent Poisson random variables with means[4]

$\lambda_i=\frac{(r-1)^i}{2i}$

## Algorithms for random regular graphs

It is non-trivial to implement the random selection of r-regular graphs efficiently and in an unbiased way, since most graphs are not regular. The pairing model (also configuration model) is a method which takes nr points, and partitions them into n buckets with r points in each of them. Taking a random matching of the nr points, and then contracting the r points in each bucket into a single vertex, yields an r-regular graph or multigraph. If this object has no multiple edges or loops (i.e. it is a graph), then it is the required result. If not, a restart is required.[5]

A refinement of this method was developed by Brendan McKay and Nicholas Wormald.[6]

## References

1. ^ Béla Bollobás, Random Graphs, 2nd edition, Cambridge University Press (2001), section 2.4: Random Regular Graphs
2. ^ Bollobás, section 7.6: Random Regular Graphs
3. ^ Bollobás, section 10.3: The Diameter of Random Regular Graphs
4. ^ Bollobás, section 2.4: Random Regular Graphs (Corollary 2.19)
5. ^ N. Wormald, "Models of Random Regular Graphs," in Surveys in Combinatorics, Cambridge University Press (1999), pp 239-298
6. ^ B. McKay and N. Wormald, "Uniform Generation of Random Regular Graphs of Moderate Degree," Journal of Algorithms, Vol. 11 (1990), pp 52-67: [1]