[Math] Number of non isomorphic graphs

graph theorygraph-isomorphism

Let $S$ be a set of all graphs with 30 vertices and 432 edges. Find how many of them are mutually non isomorphic.

My approach: we can look at their complements instead. Since $K_{30}$ has ${{30}\choose{2}} = 435$ edges, complements therefore are graphs with 30 vertices and 3 edges.

Now I'm stuck. The answer should be 5, but I have no idea how to get to it. Can you nudge me towards the right direction?

Best Answer

Think about how many graphs you can make on a graph with $V = 30$ and $E = 3$. You could have a path with three edges, a path with two edges and a path with one edge, three isolated edges, a triangle, and a star.