2
$\begingroup$

To clarify, the question has been asked on this site. However, I have a follow up question about the answer (but could not comment - since I am new to this forum).

The question: Count the number of non-isomorphic 6-regular graphs on 9 vertices.

The answer can be found here: Count the number of non-isomorphic 6-regular graphs on 9 vertices.

To summarize, the number of simple graphs with that property is the same as it's complement. I am wondering why is that the case.

$\endgroup$
1
$\begingroup$

Since isomorphims map edges to edges, and non-edges to non-edges, two graphs are isomorphic if and only if their complements are isomorphic. See e.g. Graph Theory, complements of isomorphic graphs are isomorphic.

Thus, if we take a set of representatives from each isomorphism class of $2$-regular $9$-vertex graphs and take their complements, we get non-isomorphic $6$-regular $9$-vertex graphs. Likewise, if we take a set of representatives from each isomorphism class of $6$-regular $9$-vertex graphs and take their complements, we get non-isomorphic $2$-regular $9$-vertex graphs.

This has the consequence that the set of non-isomorphic (or unlabelled) 6-regular 9-vertex graph $$\{\text{unlabelled $6$-regular $9$-vertex graph } G\}$$ is equal to the set of non-isomorphic 2-regular 9-vertex graph after replacing each graph by its complement $$\{G^c:\text{unlabelled $2$-regular $9$-vertex graphs } G\}.$$

$\endgroup$
1
$\begingroup$

The complementation map sending a graph to its complement is a bijection. Two sets have the same cardinality iff there exists a bijection between them.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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