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).

  • $\begingroup$ 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$ $\endgroup$ Jul 1, 2015 at 6:41
  • $\begingroup$ @MartinVatshelle: Yes, you're right, I meant regular graphs. Also fixed the 8. $\endgroup$
    – bitmask
    Jul 1, 2015 at 8:18
  • $\begingroup$ google.fr/… $\endgroup$
    – Lamine
    Jul 1, 2015 at 11:04
  • $\begingroup$ @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.... $\endgroup$
    – usul
    Jul 1, 2015 at 15:48

2 Answers 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.

  • 1
    $\begingroup$ 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. $\endgroup$
    – bitmask
    Jul 1, 2015 at 16:11

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.