# How to list graphs systematically?

I'm working through Wilson's "Introduction to Graph Theory" and came across this question: "List all cubic graphs with at most 8 vertices". What I've done so far, is to rule out graphs with odd vertices, since $3$-regular graphs must have an even number of vertices. Then, I figured that that the smallest such graph must be of $4$ vertices, since even complete graphs of smaller vertices cannot be $3$-regular. And the only $4$-vertex graph that is $3$-regular is the complete graph $K_4$. But after this, I'm not sure how to list out the remaining $6$-vertex and $8$-vertex cubic graphs, ensuring that I don't include isomorphic graphs. Randomly, I was able to figure that the complete bipartite graph $K_{3,3}$ is 3-regular, and so is the $3$-cube $Q_3$, but I was wondering if there was a systematic way to list all such graphs.

So, I guess my question is: How do I list graphs systematically in general, without bringing in isomorphic graphs accidentally?

• I think your restriction to 'not isomorphic graphs accidentally' is somehow just not possible. You may possibly mean not using particular machinery like group-theoretic counting arguments (Polya counting) but that is a different thing. – Mitch Dec 24 '13 at 14:29
• The easiest way to deal with the cubic graphs on six vertices is to note that any such graph is the complement of a 2-regular graph on six vertices, These are easy to classify. (This does not help with eight vertices.) – Chris Godsil Dec 24 '13 at 15:03

Let us take $n = 6$ and let $G$ be a cubic graph of order $6.$ What you can do is split your analysis depending on some invariants of $G.$ Following is an example of this.
If $G$ is bipartite then (since bipartitions of a regular graphs have to have the same size) you're left with only one choice $G = K_{3,3}.$ If $G$ is not bipartite then it has to contain an odd cycle and clearly its girth has to be $3.$ Now if $T$ is a triangle of $G$ then every vertex of $T$ has precisely one neighbor not in $T$ and after adding these neighbors you have just one way to complete the obtained graph to a cubic one.
I hope this is useful to you in case you wish me to write the same analysis for $n = 8$ let me know.