# all non-isomorphic graphs with some parameters

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?

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$

• wow.. really, but what about degree condition. Is finding all graph under 7 vertices and 5 edges with degree less then 4 equal to initial problem? – M. Red Nov 28 '17 at 17:31
• @M.Red Finding all graphs with $7$ vertices and $5$ is equivalent to the original problem. If you want to find only the graphs where each vertex has degree $\ge 4$ then in the equivalent problem you have to find all the graphs where the degree $\le 2$. – Stefan4024 Nov 28 '17 at 17:36
• @M.Red You can check my update. I think it completely adresses and answers your question – Stefan4024 Nov 28 '17 at 17:43
• So, yeah. And also it looks like I might have guessed it myself:) thanks. Can you suggest me some good modern book like this 'Intro to graph'? – M. Red Nov 28 '17 at 17:53
• @M.Red Well I don't know how good my recommednation will be, as I don't consider myself very good in graph topics. Nevertheless I have acquired all my knowledge about graphs from "Introduction to Graph Theory" by Douglas West and "A Walk Through Combinatorics" by Miklos Bona – Stefan4024 Nov 28 '17 at 18:02

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.