$3$-regular graphs and isomorphisms

20 Views Asked by At

Find all nonisomorphic $3$-regular graphs on $8$ vertices.

I know one possible graph is two tetrahedrons, since tetrahedrons are 3-regular graphs on 4 vertices. It also seems that this graph is the only disconnected graph, though I'm not sure how to prove this. But how can one systematically find these graphs? I know that we can label the vertices $v_1,\cdots, v_8$ and assume WLOG that $v_1$ is adjacent to $v_2, v_3, v_4.$ However, the remaining $4$ vertices all need to be connected to $3$ other vertices and there seems to be way too many cases to consider.