Skip to main content
1 of 2
gowers
  • 29k
  • 29
  • 145
  • 182

Wouldn't an inclusion-exclusion sort of method work here? You first count all labelled graphs. You then observe that you have overcounted: for example, every graph with rotational symmetry of order 3 has been counted three times when it should have been counted once, so you subtract twice the number of graphs with rotational symmetry 3 (which is easy to calculate because you can partition the edges into equilateral triangles and each triangle either goes in completely or not at all). But in doing this, you find that you have subtracted too much. For instance, if a graph has rotational symmetry of order 6 then it also has rotational symmetry of order 2 and 3 so you have subtracted a total of 1+2+5=8 instead of just 5. So you look at pairs of symmetry properties and add back in, and so on.

I haven't checked that this really does the job, but it feels like the sort of territory where inclusion-exclusion comes in.

gowers
  • 29k
  • 29
  • 145
  • 182