# IsomorphicGraphQ fails to recognize that two empty graphs are identical

Bug introduced in 9.0.1 or earlier and fixed in 11.0.1

Consider the following two graphs:

g1 = Graph[{1, 2, 3}, {}];

g2 = SimpleGraph@Graph[{1, 2, 3}, {1 <-> 1}];


They are clearly the same thing because SimpleGraph will remove the self loop (only edge) from g2.

Yet IsomorphicGraphQ disagrees:

IsomorphicGraphQ[g1, g2]

(* False *)


I believe this is a bug and it exists in all of 9.0.1 through to 10.4.0.

Is there a workaround?

• Given the example of Compress/Uncompress I agree that this is a bug and I added that tag accordingly. – Mr.Wizard Jul 19 '15 at 10:55
• @Mr.Wizard, given your geo, any chance you can be in Pasadena early Aug for a day? ... Szabolcs, I'd extend the same invite but you're a bit further @ away this time. – alancalvitti Jul 19 '15 at 12:30
• @alancalvitti I don't think that will be possible but I must say I am curious why you ask. – Mr.Wizard Jul 19 '15 at 12:53
• @Mr.Wizard, you already know why: software is eating the world and M.SE is a global lever. Take a look at some of the tech in this useful fiction like Ghost Fleet >> bit.ly/1e7MJ38. If you like it I'll msg you a 2-part key w/ info. – alancalvitti Jul 20 '15 at 17:15
• @alancalvitti is this poetry? – shrx Oct 16 '15 at 12:13

A simple workaround is to re-build the graph object by cycling it through some other representation. Here are two possible solutions:

rebuildGraph[g_] := Uncompress@Compress[g] (* solution 1 *)
rebuildGraph[g_] := Graph[VertexList[g], EdgeList[g]] (* solution 2 destroys properties but it's fine for isomorphism testing purposes *)

isomorphicGraphQ[g1_, g2_] :=
IsomorphicGraphQ[rebuildGraph[g1], rebuildGraph[g2]]


Now this gives a correct result:

isomorphicGraphQ[g1, g2]
(* True *)