Number of non-isomorphic graphs

discrete mathematicsgraph theorygraph-isomorphism

A graph on 8 vertices, each has degree 5. I need to find the number of such graphs, which are non-isomorphic.
So, it's easy to show, that there are $|E| = \frac{8 \cdot 5}{2} = 20$ edges in such graphs, then it's easier to take the complement of such a graph into account (because if two graphs are isomorphic, then their complements are too). It has ${8 \choose 2} – 20 = 8$ edges. From this point I can see only 3 non-isomorphic graphs on 8 vertices with 8 edges: $C_8$, $C_7$ + 1 vertex connected to any other, $C_6$ + 2 vertices connected to any vertex/different vertices in the cycle. Am I missing anything? Or maybe my reasoning is wrong?

Best Answer

In the complement, each vertex has degree $2$, so we have one of

  • $C_8$
  • $C_5+C_3$
  • $C_4+C_4$

I.e., we are looking for the number of ways to write $8$ as sum of (unordered) summands $\ge3$.

Related Question