Isomorphic Graphs

Two graphs which contain the same number of graph vertices connected in the same way are said to be isomorphic. Formally, two graphs and with graph vertices are said to be isomorphic if there is a permutation of such that is in the set of graph edges iff is in the set of graph edges .

Canonical labeling is a practically effective technique used for determining graph isomorphism. Several software implementations are available, including nauty (McKay), Traces (Piperno 2011; McKay and Piperno 2013), saucy, and bliss, where the latter two are aimed particularly at large sparse graphs.

The equivalence or nonequivalence of two graphs can be ascertained in the Wolfram Language using the command IsomorphicGraphQ[g1, g2].

Determining if two graphs are isomorphic is thought to be neither an NP-complete problem nor a P-problem, although this has not been proved (Skiena 1990, p. 181). In fact, there is a famous complexity class called graph isomorphism complete which is thought to be entirely disjoint from both NP-complete and from P.

A polynomial time algorithm is however known for planar graphs (Hopcroft and Tarjan 1973, Hopcroft and Wong 1974) and when the maximum vertex degree is bounded by a constant (Luks 1982; Skiena 1990, p. 181).

In some sense, graph isomorphism is easy in practice except for a set of pathologically difficult graphs that seem to cause all the problems. So, unlike knot theory, there have never been any significant pairs of graphs for which isomorphism was unresolved. In fact, for many years, chemists have searched for a simple-to-calculate invariant that can distinguish graphs representing molecules. There are entire sequences of papers in which one author proposes some invariant, another author provides a pair of graphs this invariant fails to distinguish, and so on. Unfortunately, there is almost certainly no simple-to-calculate universal graph invariant, whether based on the graph spectrum or any other parameters of a graph (Royle 2004).