Number of non isomorphic graphs

Question

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?

Answer 1

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.

Answer 2

The non-isomorphic 3-edge graphs without isolated vertices can be found by hand:

We can do this by:

• Take an edge $K_2$.
• Add an edge to it in all possible ways, giving $2K_2$ and the 2-edge path $P_2$.
• Add an edge to $2K_2$ and the 2-edge path $P_2$ in all possible ways, to obtain the above.

From these we add isolated vertices until we obtain 30 vertices. This gives non-isomorphic 30-vertex 3-edge representatives. From these, we take the complement to obtain the non-isomorphic 30-vertex 432-edge representatives.