Graph isomorphism is a hard problem; that is to say, it is NP-complete. It is one of those problems that could take millions of computers millions of years to solve, even though constructing a problem takes only a moderate amount of time and space. A graph is a collection of vertices connected by a collection of edges. Every edge connects exactly two vertices, but not all pairs of vertices are (necessarily) connected by an edge. Some graphs are isomorphic to other graphs, meaning:

For isomorphic graphs G and H, there exists a one-to-one function F such that:

• The domain of F is the set of vertices of G.
• The range of F is the set of vertices of H.
• If and only if [g1,g2] is an edge in G, [F(g1),F(g2)] is an edge in H.

Obviously enough, if G and H do not have the same number of vertices and edges as each other, they are not isomorphic. But assuming G and H meet this minimum condition of "plausible" isomorphism, determining whether they really are isomorphic basically means attempting every mapping from G onto H, and checking whether it creates an isomorphism.

What this boils down to is that if someone tells you he has two isomorphic graphs with enough thousands of vertices and edges, it is because he constructed the graphs to be isomorphic -- not because he discovered the isomorphism. On the other hand, it is trivial to construct isomorphic graphs with thousands of vertices and edges; you could do it on paper without using a computer if you spent a bit of time on it! Next, let's see why all this is important.