# Why are some of the isomorphisms not bijective?

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[] 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?

• Approving.IsomorphicGraphQ[VertexReplace[g1,Normal[isos[]]],#]&/@{g1,g2} will give False – yode May 31 '16 at 17:11
• @yode so should I report as a bug? – M.R. May 31 '16 at 17:58
• As a workaround, try IGraph/M. It has superior isomorphism functionality, with many features Mathematica doesn't have and much better performance for large/hard graphs. – Szabolcs May 31 '16 at 20:01

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]



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]

• I have to say this is a wonderful package.Thanks very very much. – yode May 31 '16 at 20:30

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}