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?
Best Answer
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.
Rather than having two isomorphic graphs, it seems to be easier to think in terms of how many automorphisms from a graph to itself there are. I don't know any easy systematic way to count that (in fact the references I can google up look like it is just as hard as deciding graph isomorphisms, which is suspected to be impossible in polynomial time).
In this particular case, it is fairly easy to see there are exactly 4 isomorphisms -- you can permute the two degree-2 nodes freely, and for each choice here you get a free choice of permutation for the two nodes of degree 3. But you can't send any node with one arity to one with another.