1
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – M. Red Nov 28 '17 at 17:31
  • $\begingroup$ @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$. $\endgroup$ – Stefan4024 Nov 28 '17 at 17:36
  • $\begingroup$ @M.Red You can check my update. I think it completely adresses and answers your question $\endgroup$ – Stefan4024 Nov 28 '17 at 17:43
  • $\begingroup$ 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'? $\endgroup$ – M. Red Nov 28 '17 at 17:53
  • $\begingroup$ @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 $\endgroup$ – Stefan4024 Nov 28 '17 at 18:02
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.