Wish more readable information from IsomorphicGraphQ

Question

In graph theory, an isomorphism of graphs $G$ and $H$ is a bijection between the vertex sets of $G$ and $H$ ${\displaystyle f\colon V(G)\to V(H)}$ such that any two vertices $u$ and $v$ of $G$ are adjacent in $G$ if and only if ${\displaystyle f(u)}$ and ${\displaystyle f(v)}$ are adjacent in $H$. We know that IsomorphicGraphQ can return True if two graphs $G$ and $H$ are isomorphic, False otherwise. We can use FindGraphIsomorphism to find an isomorphic mapping of $G$ and $H$.

My problem is that if two graphs are not isomorphic, the IsomorphicGraphQ will only return False. Its correctness cannot be checked manually. I was wondering if IsomorphicGraphQ could give some additional information to help us understand why these two graphs are not isomorphic.

The following just a simple example. We can say that the first graph has a cycle and the second graph has no cycle, so the two graphs are not isomorphic.

g = CycleGraph[5];
h = PathGraph[Range[5]];
IsomorphicGraphQ[g, h]

I actually came across the next two planar graphs.

G1 = Graph[
   ImportString["W{`I@CoC?o`_@_?o?K?@`?C??KG?K??EC?@_??EG??[???N", 
    "Graph6"], VertexLabels -> Automatic];
G2 = Graph[
   ImportString["WspB@CoC?o`_@@@_?GGB??KC?O??WG?CK?B_??K???W_??N", 
    "Graph6"], VertexLabels -> Automatic];
IsomorphicGraphQ[G1, G2]

False

In general, I trust the results returned by IsomorphicGraphQ, but I wish it can provide more readable information.

Answer 1

Here are some ideas that might work.

We are looking for a computation that is simple enough that we can trust its output, and can potentially show that two graphs are non-isomorphic. The simplest way is to look at the vertex degrees. In your example, they are the same: both G1 and G2 are 4-regular. But we can also count 2nd, 3rd, etc. neighbours, and see if we discover a difference. One easy way to do it is with IGConnectNeighborhood from IGraph/M, which connected each vertex to all vertices no more than distance k away. The size of the 2nd order neighbourhood is 11 for all vertices for both graphs. But for the 3rd order neighbourhood, we see differences:

VertexDegree@IGConnectNeighborhood[G1, 3]
(* {18, 19, 18, 18, 18, 19, 19, 18, 18, 19, 18, 18, 19, 18, \
18, 19, 19, 18, 18, 18, 18, 19, 18, 18} *)

VertexDegree@IGConnectNeighborhood[G2, 3]
(* {18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, \
18, 18, 18, 18, 18, 18, 18, 18, 18, 18} *)

This proves, in a reasonably straightforward manner, that the two graphs are no isomorphic.

---

An interesting question, which I do not have the answer to, is: Is there a pair of non-isomorphic graphs where the number of neighbours is identical at all distances?

Update: There are pairs of graphs where the number of neighbours is the same at all distances. The smallest example seems to be this pair:

g1 = IGShorthand["1,2,3,4,5,2-1-3-4-2,1-5-4"]
g2 = IGShorthand["1,2,3,4,5,1-4-3-2-1-5-4"]

Let us write a "signature" function that takes a connected undirected graph and counts the number of neighbours at each distance up to the diameter:

sig[g_] := Module[{dm, diam},
  dm = GraphDistanceMatrix[g];
  diam = Max[dm];
  Sort[Lookup[Counts[#], Range[diam], 0] & /@ dm]
]

This is the same for the above two graphs. Without sorting, the signature is {{3, 1}, {2, 2}, {2, 2}, {3, 1}, {2, 2}} for both graphs, yet they are not isomorphic: g1 does not have a cycle of length 3, but g2 does.

A more interesting example pair of regular graphs is ImportString["FFzvO\nFUzro" , "Graph6"].

---

It is useful to note that many isomorphism testing programs, including the one used by Mathematica, as well as Bliss (exposed through IGraph/M), compute a canonical form of graphs. See CanonicalGraph and IGBlissCanonicalGraph, IGBlissCanonicalLabeling, IGBlissCanonicalPermutation. Two graphs are isomorphic precisely when their canonical form is the same.

In my opinion, however, checking that the canonicalized forms are different does not provide additional confidence that the graphs are not isomorphic. The canonical labeller could be buggy as well.