3
$\begingroup$

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

| cite | improve this question | | | | |
$\endgroup$
  • $\begingroup$ @RushabhMehta all of them are non isomorphic ! $\endgroup$ – Random Nov 6 '18 at 17:26
  • $\begingroup$ 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. $\endgroup$ – Don Thousand Nov 6 '18 at 17:26
  • $\begingroup$ @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 $\endgroup$ – Random Nov 6 '18 at 17:32
  • $\begingroup$ I said that graph 1 doesn't have a cycle of length 4, the other 2 do. $\endgroup$ – Don Thousand Nov 6 '18 at 17:39
  • 1
    $\begingroup$ @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. $\endgroup$ – Especially Lime Nov 7 '18 at 12:21
5
$\begingroup$

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.

| cite | improve this answer | | | | |
$\endgroup$
  • 1
    $\begingroup$ Or just quadrilaterals? $\endgroup$ – Gordon Royle Nov 7 '18 at 10:08
  • $\begingroup$ That is true as well. $\endgroup$ – Mohammad Riazi-Kermani Nov 7 '18 at 12:19
2
$\begingroup$

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

| cite | improve this answer | | | | |
$\endgroup$

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.