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?

  • $\begingroup$ 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. $\endgroup$ – Mitch Dec 24 '13 at 14:29
  • $\begingroup$ 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.) $\endgroup$ – 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.


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.