# How to show these three-regular graphs on 10 vertices are non isomorphic? The number of vertices and edges are same, with each vertex having the same degree and the degree sequence of the graph is also the same. I have even tried finding a bipartite graph in any one of them even that seems to fail.

Question- How to show the three graphs with degree sequence [3,3,3,3,3,3,3,3,3,3] are non isomorphic (see figure)?

• @RushabhMehta all of them are non isomorphic ! – Random Nov 6 '18 at 17:26
• To show the graph 1 is not isomorphic, see that there are no 4-cycles in the graph, compared to the other two which do. – Don Thousand Nov 6 '18 at 17:26
• @RushabhMehta can we say that graph 2 does not have a cycle of length 4 for all vertices but graph 3 has a cycle of length 4 for all vertices – Random Nov 6 '18 at 17:32
• I said that graph 1 doesn't have a cycle of length 4, the other 2 do. – Don Thousand Nov 6 '18 at 17:39
• @Random yes, that's right. In graph 1, there are no vertices in 4-cycles. In graph 2, some, but not all, vertices are in 4-cycles. In graph 3, all vertices are in 4-cycles. This is enough to show no two are isomorphic. – Especially Lime Nov 7 '18 at 12:21

The first graph is the only one not containing $$4$$-cycles, so it's not isomorphic to the other two. The second and third graphs are not isomorphic because the third is planar and the second contains a subdivision of $$K_{3,3}$$.