0
$\begingroup$

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:

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – WaveX
    Commented Mar 10, 2020 at 16:05
  • $\begingroup$ See here for more help $\endgroup$
    – WaveX
    Commented Mar 10, 2020 at 16:05

1 Answer 1

1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Hi, I am still a little bit confused. Would this be right? 𝑒1→𝑐1,𝑒2→𝑐3,𝑒3→𝑐5,𝑒4→𝑐2,𝑒5→𝑐4 $\endgroup$
    – Danielle
    Commented Mar 11, 2020 at 0:17
  • $\begingroup$ Check the isomorphism conditions. Do they hold? $\endgroup$ Commented Mar 11, 2020 at 9:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .