# Is there an algorithm for determining when two graphs are isomorphic?

The title says it all. Is there such an algorithm? More generally, is there an algorithm for deciding when two objects are isomorphic in a particular category?

-
My knowledge of mathematical logic is weak, but as far as I know the first problem is NP (I don't know the formal definition of NP). As for the second question, a positive answer would imply the existence of an algorithm that differentiates between non-homeomorphic topological spaces. I really doubt this. –  Amr Aug 10 '13 at 21:25
@Amr: Thanks. Would you elaborate why existence of such an algorithm would imply the existence of an algorithm that differentiates between non-homeomorphic topological spaces? –  some1.new4u Aug 10 '13 at 21:29
Regarding the first problem, ofcourse there is the brute force solution. More precisely, Let $G,H$ be two graphs. If $|V(G)\not=|V(H)|$ then the two grphs can not be isomorphic. If $|V(G)|=|V(H)|$ then check all $|V(G)|!$ bijections and see if any one of them is a graph homomorphism –  Amr Aug 10 '13 at 21:32
Ah I see. Without good restrictions on your category you will get trivial answers. For example, Consider the category $\scr{C}$ that has one object. For this category, we know an algorithm that can tell us if two objects are isomorphic or not. –  Amr Aug 10 '13 at 21:42

The upper triangle of a graph $G$ on $n$ vertices can be written out as a binary sequence of length $n(n-1)/2$, and hence as a binary integer. From the $n!/|\mathrm{Aut}(G)|$ distinct graphs isomorphic to $G$, choose the one that gives the least integer. This is an invariant of the isomorphism class, two graphs are isomorphic if and only if they give rise to the same integer.