How to determine if two graphs are Isomorphic ? Finding a one to one and onto function.

Question

I have these two graphs here:

I wish to determine if they are Isomorphic. I know that I need to find a one to one and onto function, however I can't find a way to do it.

My questions are:

1. I know that these two are isomorphic. What is the function f ?
2. In general, is there a way to find these functions ? Maybe using matrices ?

Answer 1

1. In this example there are multiple possible isomorphism functions $f$. For example $f(u_1) = v_1, f(u_2) = v_4, f(u_3) = v_2, f(u_4) = v_5, f(u_5) = v_3$, or $f(u_1) = v_2, f(u_2) = v_4, f(u_3) = v_1, f(u_4) = v_3, f(u_5) = v_5$, there are $10$ such isomorphism functions for these two labeled graphs. This number is different for different graphs. (It is known that counting number of isomorphism functions is polynomially-time equivalent to checking existence of any.)
2. In comments you have a good link to the existing answer about how to do it. I want to add that graph matrices give you some invariants. Each of them can be used to show that some certain pairs of graphs are non-isomorphic. But none is known to be a criterion. Particularly, there are pairs of non-isomorphic strongly co-spectral graphs, that are co-spectral graphs with co-spectral complements. (Co-spectral graphs have the same spectrum of adjacency matrix.)

Answer 2

For this problem swap the vertices $v_1$ and $v_3$ then move them both below $v_5$ and $v_4$. Now we're untangled the second graph so that it's also a pentagon. To construct our isomorphism $\varphi$ we first choose $\varphi(u_1)=v_5$ and map the cycle $u_1,u_2,u_3,u_4,u_5$ to the cycle $v_5,v_2,v_4, v_1, v_3$ which gives an isomorphism.

Note that this isomorphism is not unique as we can choose any vertex for $\varphi(u_1$) and we can also reverse the orientation of the cycle. For small graphs like this deforming one to look like the other is a simple way to find isomorphisms. You can see if we swap $u_4$ and $u_5$ then move them above $u_1$ and $u_3$ that they form the star so we could have deformed them the other way too.