4

enter image description here

Im doing practice problems to study for an exam.

So Let's assign the four degree vertices together e and 6 so e-6. Then e is adjacent to d, b, f, h and 6 is adjacent to 1, 4, 5, 8 so assign d-1, b-4, f-5, h-8 (fine via symmetry). 4 and 1 are both adjacent to a so a-3. Then a and d are adjacent to g like how 3 and 1 are adjacent to 2 so g-2. Then 5 and 8 are adjacent to 9 like how f and h are adjacent to i so i-9. and that leaves c-7.

So the graphs are isomorphic. The isomorphism is a-3, b-4, c-7, d-1, e-6, f-5, g-2, h-8, i-9.

However, the textbook answer says

a-3, b-4, c-7, d-1, e-6, f-8, g-2, h-5, i-9. Which does not exactly match my answer.

Now some users have told me that there exists more then one correct isomorphism. But how can I tell if the isomorphism I have is right? Also is my reasoning okay?

  • Isomorphism is bijection between vertex sets where adjacent vertex edges are preserved. So according to your isomorphism, for edge f-c there must be 5-7 edge but there is 8-7 edge actually. Think it like looking at a expanded wireframe wallet from the top in the first graph and it's wires are stretched and twisted in the second one. – lockedscope Sep 29 '20 at 17:35

1 Answers1

2

It's easiest to check whether your answer is correct by drawing one graph, then label the nodes by what your isomorphism tells you it should correspond to in the other graph. Then you can easily just check neighbors for each vertex in turn.

In your case, cf is an edge, but your isomorphism candidate maps that to 75, which is not an edge on the right-hand graph.

It's good thinking on the four-degree vertex. Next, remember that an isomorphism must also, among other things, map triangles to triangles. That narrows down the search for isomorphisms a lot in this case, as the two triangles adg and cfi must map to the two triangles 123 and 789. It's quite clear this way that f-5 cannot be realized.

Arthur
  • 199,419
  • Sorry, but this stuff isn't intitutive at all to me. I see clear as day that 123 and 789 are triangles. But how can I tell that adg and cfi are triangles? –  Sep 29 '20 at 16:39
  • 1
    @TotomaLover2312 In a drawn graph, the fact that edges bend are of no consequence. A triangle is merely any loop of length 3. There are edges ad, dg and ga. This makes adg a triangle. Same for cfi. If you want, you can move d and f slightly towards e, and straighten out ag and ci. This would make the triangles look more like classic, geometric triangles. – Arthur Sep 29 '20 at 16:48