# Determining isomorphism of graphs

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.

-

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$.

-
It didn't initially appear to me that the complements would be less complex than the original graphs, or even easy to draw. So, thank you for your enlightening suggestion! – Ryan Feb 14 '13 at 8:00
The first thing I noticed was that the complements have fewer edges than the originals, so must be at least a bit easier to deal with. The second thing I noticed was that the complements were $2$-regular, and $2$-regular graphs are very easy to classify indeed. – Chris Eagle Feb 14 '13 at 10:24
You mean $\frac{7*6}2-14=7<14$? – Ryan Feb 14 '13 at 16:05

As for the general question: No efficient general procedure is known for determining whether two graphs are isomorphic.

The graph isomorphism problem is somewhat famous for being one of the few problems in NP that are suspected not to have a polynomial-time algorithm, yet haven't been proved NP-complete.

-

Just to share one observation using graph coloring:

$G_1\cong G_2\implies \chi(G_1)=\chi(G_2)$

So you can actually show that $G_1\not\cong G_2$ and $G_1\not\cong G_3$.
This is because $\chi(G_1)=4$ and $\chi(G_2)=\chi(G_3)=3$.

A 3-coloring of $G_2$ (left-to-right, then down):
$\lbrace 1,2,2,3,3,1,1\rbrace$

A 3-coloring of $G_3$ (same orientation):
$\lbrace 3,2,2,1,3,1,2\rbrace$

And one may prove that $\chi(G_1)> 3$ by starting with the coloring:
$\lbrace 1,2,2,3,3,1,?\rbrace$

But the converse is not true.
If $\chi(G_1)=\chi(G_2)$, it need not be that $G_1\cong G_2$.
(Think 1 big even cycle against 2 small even cycles)

However, you can discover the "right way" to label the graphs guided by the coloring.
Because under the right labeling, you must have a same way of coloring.
Then checking edges pairwise gives you the isomorphism...

Certainly not an efficient method for this problem.
Perhaps not efficient in general too.

-
Thanks! Will check back on your answer after I've learnt graph colouring. Am now just at the very beginning of Graph Theory :) – Ryan Feb 14 '13 at 16:11
Same as me! I am currently taking Graph Theory too. (Although I have read a little in the past) I wanted to try the line graph method but it is so tedious to draw... – Yong Hao Ng Feb 14 '13 at 18:51

You can check if two graphs are not isomorphic by looking at the spectrum of the adjacence matrix...

-
Isospectral graphs need not be isomorphic: MathWorld gives the example of $C_4 \cup K_1$ and $K_{1,4}$. – Andrew Uzzell Feb 13 '13 at 16:08
@AndrewUzzell isn't that exactly what I say? – draks ... Feb 18 '13 at 11:19