0

I am currently trying to seek assistance in regards to graph isomorphism. I believe the graphs are indeed isomorphic as they both have 5 vertices, 5 edges and a degree of 2.

However, I just want to verify besides what I have mentioned is there anything else that I would need to look at to make sure these graphs are isomorphic? I believe you need to map each vertex in Graph 1 to the adjacent vertex in Graph 2 but I do need some assistance with that if anybody is willing to explain that part to me? I have attached a picture of the example also:

Danielle
  • 1
  • You have the right idea. Once you have mapped each vertex in the first graph to is appropriate vertex in the second, you must show that this mapping preserves adjacency between appropriate vertices. – WaveX Mar 10 '20 at 16:05
  • See here for more help – WaveX Mar 10 '20 at 16:05

1 Answers1

1

Let $G_1 = (V_1,E_1)$ and $G_2 = (V_2,E_2)$. You must define the isomorphism, which is a function $f : V_1 \rightarrow V_2$, respectively, and show that it satisfies the definition of a graph isomorphism, that is, that $f$ is a bijection and satisfies that if $\{ u,v\} \in E_1$, then $\{ f(u), f(v) \} \in E_2$. Hint: Let $f(e_1) = c_5$.

Hans Hüttel
  • 4,271