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?
Number of non-isomorphic graphs
discrete mathematicsgraph theorygraph-isomorphism
Best Answer
In the complement, each vertex has degree $2$, so we have one of
I.e., we are looking for the number of ways to write $8$ as sum of (unordered) summands $\ge3$.