all non-isomorphic graphs with some parameters

Question

How to draw all non-isomorphic graphs with 7 vertices and 16 edges. Also all vertices have degree greater or equal to 4. Are there some general method to determine some kind of problem?

Answer 1

HINT: Note that $G_1 \cong G_2 \iff \overline{G_1} \cong \overline{G_2}$. So the problem reduces to finding all non-isomorphic graphs on $7$ vertices and $5$ edges. This should be much simpler.

---

If you want all vertex to have at least degree $4$ in $G$, then you need every vertex to be of degree at most $2$ in $\overline{G}$. This means all connected components are trees (moreover paths). So as $7-5=2$ $\overline{G}$ is a forest of 2 trees (paths). So basically the problem comes down to determing in how many ways you can write $7$ as a sum of two positive integers. There are $3$ such possiblilites, namely $6+1=5+2=4+3 =7$. So the three non-isomorphic graphs are:

$$P_1 \cup P_6 \quad \quad P_2 \cup P_5 \quad \quad P_3 \cup P_4 \quad \quad$$

Now just take their complements to find the wanted graphs on $7$ vertices, $16$ edges and all vertex degrees $\ge 4$

Answer 2

Given the simpler problem from Stefan4024's answer, it can be broken down further like this:

1. List all partitions of 10 (twice the number of edges) into 7 parts (the number of vertices)
2. Use these partitions as input to the Havel-Hakimi theorem to get a connected graph

This will give you some candidates that can be rejected or added to until you have all the graphs.