Encyclopedia

Random regular graph

Wikipedia contributorsAdapted for Fathomly · View authors

1 min read
Source updated May 7, 2025

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\leq 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.

01Properties of random regular graphs

As with more general random graphs, it is possible to prove that certain properties of random $m$ , regular graphs hold asymptotically almost surely. In particular, for $r\geq 3$ , 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 $\epsilon >0$ is a positive constant, and $d$ is the least integer satisfying

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

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\geq 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

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

02Algorithms 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.

Watch videos about Random regular graphExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Random regular graph”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.