A way to generate a random -regular graph is via the configuration model. Here is a short description of the model. Imagine that each vertex has k tokens. This suggests that we have in total kn tokens, where is the number of vertices and you can freely think of . Also, let me mention that in whatever follows, is a constant. Then we pair up tokens randomly. Of course we will assume that when is odd, that is even, otherwise the pairing is impossible. Then, we project the configuration in a multigraph in the obvious way, which I describe by an example: if the pair between token of vertex pairs with the token of vertex then we add an edge between . A nice way to visualize the configuration model is via the following picture where the tokens are coordinates on the x-axis [bucketed according to which vertex they belong to] and the pairings are shown via the semicircles:
If anyone wants the MATLAB script before I clean it up just let me know. How many such configurations exist? Let’s call their number to denote that it is a function of and . Well, consider the last token on the x-axis, i.e., the token . It will have to pair with one token. How many choices does it have? Clearly, . Therefore We obtain the obvious recurrence where . The solution to this recurrence has a name, since it is an important recurrence. The name is double factorial. Namely, . In a follow up post, I will write more on different existing methods to generate -regular graphs. For now, remember that this technique is good for generating regular graphs when is small, since as increases, the probability of the graph being simple decreases exponentially, and that will force us to execute the pairing exponential number of times.