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.
 A: 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$.
A: 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.
A: 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.
A: You can check if two graphs are not isomorphic by looking at the spectrum of the adjacence matrix...
