# Probability of arising of simple graph in configuration model

I am studying a configuration model building $$d$$-regular graphs and reading the following article: The expansion of random regular graphs by David Ellis.

I am stuck on the following step:

Each simple labelled $$d$$-regular graph on $$n$$ vertices has the same probability of arising. Indeed, it is easy to see that a simple d-regular graph on $$[n]$$ arises from precisely $$(d!)^n$$ of the matchings.

Where does this $$(d!)^n$$ come from?

• Given one representation of a particular simple graph, how many equivalent representations are there? How would you generate them? Can you count them? If you get lost, try working out a simple example, say 2-regular simple graphs on 3 vertices. Mar 4, 2021 at 16:20
• A quite related question was posted here: mathoverflow.net/questions/360848/… Mar 5, 2021 at 20:26

Consider a simple $$d$$-regular graph. For each vertex, assign numbers from $$1$$ to $$d$$ to the edges adjacent to it. There are $$(d!)^n$$ ways to do so. Each such assignment corresponds to a particular perfect matching in the configuration model, and vice versa.