# Finding all mapping between two isomorphic graphs

Is there any formula for counting all the mappings between two isomorphic graphs? I have the following two graphs. and I am trying to find the mappings in the following way.

For each edge in $G_1$, I map it to one of the five edges of $G_2$. For each such mapping there are two options for vertex mapping. For example, for $(1,2)_{G_1}$, I pick the edge $(1, 4)_{G_2}$. So, the vertex mappings are $(1_1 \mapsto 1_2, 2_1 \mapsto 4_2)$ and $(1_1 \mapsto 4_2, 2_1 \mapsto 1_2)$. Here $i_j$ is the $i$-th vertex of $G_j$.

For each option, I fix these two vertex mappings first and then I get two other mappings for the rest two vertex-to-vertex correspondences.

So, $(1,2)_{G_1}$ is mapped to $(1,2)_{G_2}$, $(1,3)_{G_2}$, $(1,4)_{G_2}$, $(4,2)_{G_2}$ and $(4,3)_{G_2}$. For each of them I get two options. So, in a total I am getting $10$ mappings of graph isomorphism for $G_1$ and $G_2$.

Am I doing it right?

No, you cannot map an each edge in $G_1$ to an arbitrary one in $G_2$. For example the 1-4 edge in your $G_1$ connects a degree-3 vertex with a degree-2 vertex, and cannot map isomorphically to the 1-4 edge in $G_2$ which goes bewteen the two degree-3 vertices.
• In that case the mappings are: $(1_1 \mapsto 1_2, 2_1 \mapsto 2_2, 3_1 \mapsto 4_2, 4_1 \mapsto 3_2)$, $(1_1 \mapsto 4_2, 2_1 \mapsto 3_2, 3_1 \mapsto 1_2, 4_1 \mapsto 2_2)$, $(1_1 \mapsto 1_2, 2_1 \mapsto 3_2, 3_1 \mapsto 4_2, 4_1 \mapsto 2_2)$ and $(1_1 \mapsto 4_2, 2_1 \mapsto 2_2, 3_1 \mapsto 1_2, 4_1 \mapsto 3_2)$. Jul 22, 2014 at 15:27