Why are some of the isomorphisms not bijective?

Question

Bug introduced in 10.4 and fixed in 11.0.1

---

Mathematica computes all the isomorphisms between graph g1 and g2:

g1 = Graph[{1 <-> 3, 1 <-> 4, 1 <-> 6, 2 <-> 4, 2 <-> 5, 2 <-> 7, 3 <-> 5, 
 3 <-> 8, 4 <-> 9, 5 <-> 10, 6 <-> 7, 6 <-> 10, 7 <-> 8, 8 <-> 9, 
 9 <-> 10}]
g2 = Graph[{1 <-> 2, 2 <-> 3, 3 <-> 4, 4 <-> 5, 5 <-> 1, 2 <-> 6, 6 <-> 7, 
 7 <-> 8, 8 <-> 3, 9 <-> 8, 10 <-> 9, 10 <-> 4, 5 <-> 7, 1 <-> 9, 
 6 <-> 10}]
isos = FindGraphIsomorphism[g1, g2, All]

But looking at some of them confuses me, like isos[[84]] is

<|1 -> 8, 7 -> 10, 10 -> 1, 3 -> 7, 8 -> 6, 9 -> 2, 4 -> 3, 2 -> 4, 5 -> 5|>

This can't be right, here 7->10->1->8->6->? If 8 goes to 6, then what is vertex 6 mapped to? Am I missing something, or is this a problem with FindGraphIsomorphism?

Answer 1

This is a bug. The length of each association returned should be VertexCount[g1], but it isn't.

Length /@ FindGraphIsomorphism[g1, g2, All]
(* {10, 6, 8, 6, 8, 6, 9, 9, 9, 9, 6, 8, 8, 10, 8, 10, 10, 9, \
9, 10, 9, 10, 9, 10, 10, 9, 9, 10, 8, 10, 10, 9, 10, 8, 9, 10, 9, 10, \
9, 10, 10, 9, 8, 10, 9, 10, 8, 10, 10, 10, 10, 9, 8, 9, 10, 10, 6, 9, \
10, 9, 8, 9, 6, 9, 10, 10, 9, 10, 10, 9, 10, 10, 10, 10, 9, 10, 10, \
9, 6, 9, 10, 10, 8, 9, 9, 6, 9, 8, 9, 10, 10, 10, 10, 10, 10, 9, 10, \
10, 9, 10, 9, 8, 10, 10, 9, 6, 9, 10, 10, 9, 10, 10, 10, 10, 9, 8, 9, \
10, 9, 6} *)

The bug is present in M10.4.1 but not in M10.3.1.

---

As a workaround, try IGraph/M, which has superior isomorphism functionality.

To find all isomorphisms, you can use the VF2 and LAD algorithms in the package.

<<IGraphM`

IGVF2FindIsomorphisms[g1, g2]

IGLADFindSubisomorphisms[g1, g2]

The Bliss algorithm can find one isomorphism:

IGBlissGetIsomorphism[g1, g2]

Or get the number of isomoprhisms:

IGBlissAutomorphismCount[g1]
(* 120 *)

Or get the automorphism group, which can then be used to generate all isomorphisms:

group = PermutationGroup[IGBlissAutomorphismGroup[g2]]

iso = First@IGBlissGetIsomorphism[g1, g2]

AssociationThread[Keys[iso], #] & /@ (Permute[Values[iso], #] &) /@ GroupElements[group]

Answer 2

I think this is a bug of FindGraphIsomorphism.And you should give a report to Wolfram.This is what my thinking about it.

IsomorphicGraphQ[VertexReplace[g1, Normal[#]], g1] & /@ isos // Counts

<|True -> 64, False -> 56|>

---

But I still think there are work-around to find the isomorphic graph.This is my solution.

Find the permutation group all of isomorphism

permute = GraphAutomorphismGroup[g1]

PermutationGroup[{Cycles[{{2, 4}, {6, 7}, {8, 10}}], Cycles[{{2, 4,3}, {5, 6, 10, 9, 8, 7}}], Cycles[{{1, 2, 8, 7, 5, 3}, {4, 6,9}}]}]

Then check what we get

ruleYouWant = Rule @@@ Transpose[{VertexList[g1], #}] & /@ 
   Permute[VertexList[g1], permute];
IsomorphicGraphQ[VertexReplace[g1, #], g1] &/@ruleYouWant

{True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True}