0

enter image description here

So I said that the answer is yes, because the amount of 3-length cycles in each graph match so the two graphs must be isomorphic.

In order to find an isomorphism I did this.

Let's pick vertex a to correspond with vertex 1, so a-1 (fine via symmetry). a is adjacent to b,e,d like how 1 is adjacent to 2,3,6 so let's assign b-2, e-3, d-6 (also fine via symmetry). So 1, 2, and 6 are adjacent to 4 like how a,b, and d are adjacent to f, so f-4 and that makes c to be assigned to 5 so c-5.

So the graphs are isomorphic. An isomorphism is a-1, b-2, c-5, d-6, e-3, f-4

but the answer in the book says Yes, they are isomorphic. An isomorphism is a-6, b-1, c-3, d-5, e-2, f-4 which does not match my answer.

Where did I go wrong?

  • 1
    $e$ has valency $4$, but $3$ has valency $3$. – Angina Seng Sep 29 '20 at 04:40
  • 1
    Your answer is wrong, but even a correct answer need not match the answer in the book, there is more than one isomorphism! – bof Sep 29 '20 at 04:43
  • I see where I made my mistake. Okay correcting myself and starting over from the beginning now. Let's assign the 4-degree vertices to each other so b-1, then b is adjacent to a,c,e,f and 1 is adjacent to 2,3,4,6 so let's assign a-2, c-3, e-4, and f-6 (fine via symmetry). Then that leaves d to be assigned to 5 so d-5. So the graphs are isomorphic and the isomorphism is a-2, b-1, c-3, d-5, e-4, f-6. Do I have it right and how can I tell if the isomorphism I have is right? –  Sep 29 '20 at 04:48
  • 1
    Why does the equal number of triangles imply isomorphism? A hexagon with added edges going from the vertices to the center also has six triangles, but is not isomorphic to these. – Conifold Sep 29 '20 at 04:56
  • Oh so checking the amount of cycles isn't a reliable method for checking isomorphism? –  Sep 29 '20 at 05:03
  • 1
    No, it is not, see Graph isomorphism algorithm / sufficient condition. – Conifold Sep 29 '20 at 05:07
  • Thank you, but, I still wonder if my permutation of the answer is correct or not? How do I go about checking this? –  Sep 29 '20 at 05:08
  • 1
    Make adjacency matrices arranging vertices in the order given by your map, $abcdef$ and $213546$, i.e. mark entries in each matrix with $1$ if the vertices are connected by an edge and $0$ otherwise. If the matrices are identical this is an isomorphism. – Conifold Sep 29 '20 at 05:12
  • I wish I saw this earlier before I posted another question. So would the columns labels be 213546 and the row labels abcdef? so for example (2,a) = 1? Oh wait am I supposed to make seperate matrixes and not put them together I.E. One Matrix for 213546 as the row and column and One matrix for abcdef as the row and column and then compare the two? Is that what you're saying? –  Sep 29 '20 at 05:18
  • Never mind I see what you mean. Thanks! This helps a lot –  Sep 29 '20 at 05:23
  • One last question though. This check method by making these adjacency matrices works for all possible cases/questions where we have to check isomorphisms correct? –  Sep 29 '20 at 05:33
  • 1
    Yes, it is just a handy way to directly check the definition of isomorphism: corresponding vertices are adjacent by the corresponding edges. – Conifold Sep 29 '20 at 10:31
  • Got it thank you! –  Sep 29 '20 at 16:40

1 Answers1

0

Here is the short answer: $a$ can't corresponds to 1. They have different numbers of edges out from the vertex!

Ray
  • 1,280
  • I see where I made my mistake. Okay correcting myself and starting over from the beginning now. Let's assign the 4-degree vertices to each other so b-1, then b is adjacent to a,c,e,f and 1 is adjacent to 2,3,4,6 so let's assign a-2, c-3, e-4, and f-6 (fine via symmetry). Then that leaves d to be assigned to 5 so d-5. So the graphs are isomorphic and the isomorphism is a-2, b-1, c-3, d-5, e-4, f-6. Do I have it right and how can I tell if the isomorphism I have is right? –  Sep 29 '20 at 04:55