<p>The standard simple way of generating random regular graphs is:</p>

<ul>
<li>while the degree &lt; d

<ul>
<li>choose a random perfect matching from the edges still possible to add to the graph</li>
<li>If no matching is possible, restart the process.</li>
</ul></li>
</ul>

<p>The problem with this is that the higher edge degree you want, the more likely it is for the algorithm to get stuck. I see many papers limiting themself to $|V|&gt;d^3$, so I don't know if this process will work for you.</p>

CC BY-SA 3.0
2015-07-01T16:11:38.783Z
After thinking more about the problem I think I found a $n^2$-time and -space non-probabilistic algorithm that should work for all $d$ iff $|V|\cdot d$ is even and always terminates (even with an adversarial random number generator). I might post it after more scrutiny.
bitmask
CC BY-SA 3.0
2015-07-01T06:45:26.927Z
2015-07-01T06:51:36.303Z
2015-07-01T06:51:36.303Z
Martin Vatshelle
<p>Much progress was made recently in this area, see in particular this FOCS'19 paper:</p>
<pre><code>Fast uniform generation of random graphs with given degree sequences
Andrii Arman, Pu Gao, Nicholas Wormald
</code></pre>
<p>and the <a href="https://arxiv.org/abs/1905.03446" rel="nofollow noreferrer">more extensive arxiv version</a>.</p>
<p>This paper presents an <span class="math-container">$O(nd+d^4)$</span> time algorithm for <span class="math-container">$d$</span>-regular graphs when <span class="math-container">$d=o(\sqrt{n})$</span>, and <a href="https://mathoverflow.net/questions/365865/fast-uniform-generation-of-random-graphs-with-given-degree-sequences-any-imple">an implementation is provided</a>.</p>

CC BY-SA 4.0
2021-02-28T21:17:49.103Z
2021-03-01T20:27:08.207Z
2021-03-01T20:27:08.207Z
Matthieu Latapy
<p>I'm trying to find undirected random graphs $G(V,E)$ with $|V|$ = $d^2$ for $d \in \mathbb{N}$ such that $\forall v \in V: deg(v) = d$.</p>

<p>For $d \in 2\mathbb{N} +1$ this trivially is impossible as no such graph exists: The number of incidences (connections between vertices and edges) is given by $|V|\cdot d = d^3 = 8k^3 + 12k^2 + 6k + 1$ (for some $k$). As the number of incidences is always double the number of edges $|E| = d^3/2$ is a contradiction.</p>

<p>This argument however, doesn't work for $d \in 2\mathbb{N}$.</p>

<p>My first guess was just constructing a random graph would do, however, this can get stuck in a local maximum. For instance in $d = 2$:</p>

<pre><code>+---+    example for
|  /     an incomplete
| /      graph that
|/       cannot be
+   +    completed
</code></pre>

<p>A similar example can be constructed for $d = 4$ leaving up to two unconnectable vertices (essentially by using a 4-HyperCube).</p>

<p>I strongly suspect that for each $d$ the number of valid graphs significantly outweigh the number of incomplete graphs, but I would like to know <strong>how likely it is to end up with an incomplete graph</strong>. And if there is a <strong>better way to find these graphs</strong> than the random algorithm above (which could perhaps be fixed by breaking apart incomplete graphs, but that would not be guaranteed to terminate).</p>

CC BY-SA 3.0
2015-07-01T06:41:37.580Z
Do you mean degree or edge-degree? it seems from your post that you mean degree. If so such a graph is called a regular graph.
Also there is a mistake when you insert d=2k+1, it should say $8k^3$
Martin Vatshelle
CC BY-SA 3.0
2015-07-01T08:18:59.230Z
@MartinVatshelle: Yes, you're right, I meant regular graphs. Also fixed the `8`.
bitmask
CC BY-SA 3.0
2015-07-01T11:04:23.927Z
https://www.google.fr/search?q=generating+regular+graph&ie=utf-8&oe=utf-8&gws_rd=cr&ei=psiTVd3HKIG1UOX4gagB
Lamine
CC BY-SA 3.0
2015-07-01T15:48:42.313Z
@Lamine, what is the point of the link? I see several research papers (as well as blog posts, etc), but no way to tell the most up-to-date or definitive answer to the question....
usul
<graph-theory><graph-algorithms><randomness>
Finding a random regular graph with degree d
bitmask
# Finding a random regular graph with degree d

(Asked by: username_0 on 2015-06-30)

I'm trying to find undirected random graphs $G(V,E)$ with $|V|$ = $d^2$ for $d \in \mathbb{N}$ such that $\forall v \in V: deg(v) = d$.
For $d \in 2\mathbb{N} +1$ this trivially is impossible as no such graph exists: The number of incidences (connections between vertices and edges) is given by $|V|\cdot d = d^3 = 8k^3 + 12k^2 + 6k + 1$ (for some $k$). As the number of incidences is always double the number of edges $|E| = d^3/2$ is a contradiction.
This argument however, doesn't work for $d \in 2\mathbb{N}$.
My first guess was just constructing a random graph would do, however, this can get stuck in a local maximum. For instance in $d = 2$:
+---+    example for
|  /     an incomplete
| /      graph that
|/       cannot be
+   +    completed

A similar example can be constructed for $d = 4$ leaving up to two unconnectable vertices (essentially by using a 4-HyperCube).
I strongly suspect that for each $d$ the number of valid graphs significantly outweigh the number of incomplete graphs, but I would like to know how likely it is to end up with an incomplete graph. And if there is a better way to find these graphs than the random algorithm above (which could perhaps be fixed by breaking apart incomplete graphs, but that would not be guaranteed to terminate).

**Tags:** graph-theory, graph-algorithms, randomness
> **Comments:**
> **username_1**: Do you mean degree or edge-degree? it seems from your post that you mean degree. If so such a graph is called a regular graph. Also there is a mistake when you insert d=2k+1, it should say $8k^3$  
> **username_0**: @MartinVatshelle: Yes, you're right, I meant regular graphs. Also fixed the `8`.  
> **username_2**: https://www.google.fr/search?q=generating+regular+graph&ie=utf-8&oe=utf-8&gws_rd=cr&ei=psiTVd3HKIG1UOX4gagB  
> **username_3**: @Lamine, what is the point of the link? I see several research papers (as well as blog posts, etc), but no way to tell the most up-to-date or definitive answer to the question....  

---

## 2 answers

### Answer by username_1 on 2015-07-01. Score: 2

The standard simple way of generating random regular graphs is:

* while the degree < d
  + choose a random perfect matching from the edges still possible to add to the graph
  + If no matching is possible, restart the process.

The problem with this is that the higher edge degree you want, the more likely it is for the algorithm to get stuck. I see many papers limiting themself to $|V|>d^3$, so I don't know if this process will work for you.

> **Comments:**
> **username_0**: After thinking more about the problem I think I found a $n^2$-time and -space non-probabilistic algorithm that should work for all $d$ iff $|V|\cdot d$ is even and always terminates (even with an adversarial random number generator). I might post it after more scrutiny.  

---

### Answer by username_4 on 2021-02-28. Score: 0

Much progress was made recently in this area, see in particular this FOCS'19 paper:
Fast uniform generation of random graphs with given degree sequences
Andrii Arman, Pu Gao, Nicholas Wormald

and the more extensive arxiv version.
This paper presents an $O(nd+d^4)$ time algorithm for $d$-regular graphs when $d=o(\sqrt{n})$, and an implementation is provided.


---

