Random regular graphs and configuration models

For degrees d_v whose sum L is even, give vertex v exactly d_v labeled half-edges and choose a uniformly random perfect matching of all L half-edges. Each matched pair becomes an edge. Two half-edges at the same vertex produce a loop, which contributes two to that vertex’s degree. Different matched pairs between the same two vertices produce parallel edges. The sample space consists of matchings, not multigraphs; different multigraphs can correspond to different numbers of matchings, so their projected probabilities need not be equal.

For L positive and even, the number of perfect matchings is the product of the odd numbers through L−1. A specified half-edge’s partner is uniform among the other L−1 half-edges. Thus a specified pair is matched with probability 1/(L−1). Summing over pairs within each vertex gives the expected number of loops. This expectation is exact, but does not equal the probability of at least one loop unless one has ruled out multiple loops. Markov supplies only an upper bound on that probability.

Assume a simple graph with the prescribed labeled degrees exists. For each such graph, assign its incident edges bijectively to the labeled half-edges at each vertex. This gives exactly the product of d_v factorials different pairings projecting to that graph, independent of which simple graph was chosen. Consequently the configuration model conditioned on producing a simple graph is uniform over all simple labeled graphs with that degree sequence. This constant-multiplicity argument applies on the simple event, not indiscriminately across multigraphs.

For a fixed nonnegative integer d, along n with nd even and n large enough, the simplicity probability of the d-regular configuration model tends to $\exp(-(d^2-1)/4)$ when d is positive; d=0 is trivially simple. In particular it stays bounded away from zero for fixed d. Therefore an event whose failure probability tends to zero in the configuration model also holds with high probability after conditioning on simplicity. If d grows with n, that fixed-d formula and the same transfer conclusion must not be asserted without additional hypotheses.

A matching can be sampled by repeatedly choosing a partner uniformly for one unmatched half-edge. The available partner set shrinks after each step, so different pairing events are dependent. Conditional probabilities are still simple when expressed in terms of unmatched half-edges. This makes the model useful for neighborhood exploration and counting small configurations, but it does not justify independent-edge Chernoff calculations for arbitrary adjacency indicators. Fixed vertex degree itself demonstrates the dependence: one additional neighbor can constrain the remaining choices.

Exact small examples are useful checks because the limiting simplicity formula need not be accurate at small n. They also expose the distinction between a number of graphs and a number of pairings. For degree three on four labeled vertices there is only one simple graph, the complete graph. It still receives many pairing realizations because its incident edges can be assigned to labeled half-edges independently at each vertex. Counting only that one graph in the pairing sample space would severely understate its probability.