Finding a random regular graph with degree d 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).
The standard simple way of generating random regular graphs is:


while the degree &lt; 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|&gt;d^3$, so I don't know if this process will work for you.