1
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$
    – Yuval Filmus
    Mar 4, 2021 at 16:20
  • $\begingroup$ A quite related question was posted here: mathoverflow.net/questions/360848/… $\endgroup$
    – Matthieu Latapy
    Mar 5, 2021 at 20:26

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

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

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