# Count the number of non-isomorphic 6-regular graphs on 9 vertices.

I know there will be 9 vertices of degree 6, which means there are 54 edges. But then how will I figure out the number of non-isomorphic graphs?

• @The number of edges is 27. – svsring May 15 '16 at 11:31
• Ha, forgot the overcount :P. – Henry Lee May 15 '16 at 18:33

Hint: It is a lot easier to count their complements.

• I assume the complement is a 2-regular graph on 9 vertices correct? – Henry Lee May 15 '16 at 2:04
• @HenryLee: Correct, – hmakholm left over Monica May 15 '16 at 2:43
• That would mean there's only one graph though...is it only one? – Henry Lee May 15 '16 at 3:02
• @HenryLee: No, there are four. (Are you perhaps imagining that the complement has to be connected?) – hmakholm left over Monica May 15 '16 at 7:46
• Wouldn't it have to because it's 2-regular? – Henry Lee May 15 '16 at 18:33

They can be generated using geng which is packaged with Nauty using the command ./geng 9 -d6 -D6. Feeding this into showg will show the adjacencies of the graphs, which we draw as follows:

We color the non-edges red and identify the complement graphs below each graph. We can readily see why it's easier to count the 2-regular graphs and take their complements.

Since isomorphims map edges to edges, and non-edges to non-edges, two graphs are isomorphic if and only if their complements are isomorphic.