How can we determine if any pair of the following graphs are isomorphic to each other? Is there an efficient way to know for sure? The obvious things to check for (number of edges, vertices, degrees) aren't fruitful because all three graphs have the same of each. Any suggestion appreciated.
[Math] Determining isomorphism of graphs
graph theory
Related Solutions
The graph at left has a 3-cycle $(a,b,j)$ (also $(f,e,g)$). The graph at right has none. They are not isomorphic.
It may be worth noting that the graph at right is simply (the skeleton of) a pentagonal prism; consequently, each vertex is (in an appropriate sense) "equivalent" to every other vertex. This is not the case in the graph at left.
Also, the graph at right, as illustrated, is planar; no edges intersect. In the graph at left, you can replace "chords" $bj$ and $eg$ with paths that travel "outside the circle", eliminating intersections with $af$, but you can't do that with both of $ch$ and $di$ and not have $ch$ and $di$ cross; an edge intersection is inevitable (although this needs rigorous proof), so the graph is non-planar.
This a very interesting question which I am afraid has (as of the moment) a somewhat disappointing answer.
The problem of graph isomorphism has been an object of study of Computational Complexity since the beginnings of the field. It is clearly a problem belonging to NP, that is, the class of problems for which the answers can be easily verified given a 'witness'- an additional piece of information which validates in some sense the answer.
For example, given two isomorphic graphs a witness of its isomorphism could be the permutation which transforms one graph into the other.
Now for the interesting part. NP is further divided into P (polynomial time solveable) problems, NP-complete problems and NP-intermediate problems. An NP complete problem is one whose solution can be used to encode any other NP problem, meaning that if you could efficiently solve one NP-complete problem, you could efficiently solve all of them, and thus $P=NP$.
However, most researchers believe that $P\ne NP$. One of the consequences of this
is the existence of NP-intermediate problems (Ladner's theorem) - problems which
are in NP but are not in P nor NP-complete. One remarkable aspect of the proof of
Ladner's theorem is that the hypothetical language constructed is very unnatural.
It is an open problem to find an actual NP-intermediate language.
Some contenders have been disqualified as potential candidates for NP-intermediateness, but graph isomorphism is one of the remaining. We do not actually know whether GI is in P, NP-complete or NP-intermediate.
The evidence however suggests that it is either NP-intermediate or in P. There is a very recent advance, due to Babai, which shows that GI is solvable in quasi-polynomial time, which is something we would not expect from a NP-complete problem.
Hope I have not left any major detail out. Feel free to ask questions about GI or its cousin, graph non-isomorphism.
Best Answer
Two graphs are isomorphic if and only if their complements are isomorphic. The complement of $G_1$ is a $7$-cycle, while the complements of $G_2$ and $G_3$ are both the disjoint union of a $4$-cycle and a $3$-cycle. Thus $G_2$ and $G_3$ are isomorphic to each other but not to $G_1$.