Random regular graph

A random "r"-regular graph is a graph selected from formula_1, which denotes the probability space of all "r"-regular graphs on "n" vertices, where 3 ≤ "r" < "n" and "nr" is even. 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 asymptotically almost surely. In particular, for formula_2, a random "r"-regular graph of large size is asymptotically almost surely "r"-connected. 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 formula_3 > 0 is a positive constant, and "d" is the least integer satisfying
formula_4
then, asymptotically 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.
The distribution of the number of short cycles is also known: for fixed "m" ≥ 3, let "Y"3,"Y"4,…,"Y""m" be the number of cycles of lengths up to "m". Then the "Y""i" are asymptotically independent Poisson random variables with means
formula_5
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.
A refinement of this method was developed by Brendan McKay and Nicholas Wormald.