How to show these three-regular graphs on 10 vertices are non isomorphic?

2.6k Views Asked by At

enter image description here

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)?

2

There are 2 best solutions below

2
On BEST ANSWER

Count the number of quadrilaterals and the number of pentagons in each graph. ( 4-cycles and 5-cycles )

You will come up with different numbers which indicate these are not isomorphic graphs.

0
On

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}$.