Graph isomorphisms on 6 vertices with degree 3

Question

I want to find another graph that has 6 vertices and each has degree $3$ that is not isomorphic to these two graphs below. I know that these two graphs are isomorphic. They will all have the same degree sequence, So I kind of stuck how to find such graph. Any suggestions ?

Answer 1

Draw two triangles and join them with a 1-factor.

Answer 2

This graph being $3-regular$ on $6$ vertices always contain exactly $9$ edges.

One possible graph is as follows:

-Join the vertices $1,2,3,4,5,6$ by making parallel edges between each pair $1$ & $2$, $3$ & $4$, and $5$ & $6$. This will exhaust $6$ of your edges. Now join each pair $2$ & $3$, $4$ & $5$, $6$ & $1$ by using $3$ more edges. -

As this graph is not simple hence cannot be isomorphic to any graph you have given.

Answer 3

The Stefan Gyürki's answer and the author's one can solve one variant of this question. If we change the question to be more specific, we can find one nonisomorphic graph based on more conditions to use.

Find the number of nonisomorphic simple graphs with six vertices in which each vertex has degree three.

This is shown in this lecture p2. Here I give some notes for this doc.

1. Since the lecture doesn't consider the case where the vertices are splitted into 3 pairs and each pair are connected with one endpoint has one loop, here it probably assumes the 3-regular graph is one simple graph, although it is not always this case.
2. Since this is one unlabelled vertex problem, so we can assume

   Let x be any vertex of such 3-regular graph and a, b, c be its three neighbors.

3. It is splitted into 2 cases (whether $y,z$ are adjacent or not), so it will consider all possible cases.
   1. "If y and z are not adjacent", based on the assumption of the specific question, loops are excluded. So only the bipartite is possible.
   2. "By symmetry" is due to the assumption of "unlabelled vertex problem".

---

we can also use the bof's answer to solve the above specific variant.

Based on this, if we exclude all loops (then only 1-(i),2-(i,ii),3-(i) are left) and all parallel edges (then only 1-(i),2-(i) are left), then we has only 2 graphs. This is same as the above method.

Answer 4

A graph on $6$ vertices is regular of degree $3$ if and only if its complement is regular of degree $2.$

First find two nonisomorphic $2$-regular graphs on $6$ vertices (hint: one is connected, the other is not); their complements will be nonisomorphic $3$-regular graphs on $6$ vertices.