# Can someone intuitively explain how we can tell if two graphs are isomorphic?

I'm having a hard time understanding the explicit definition and was hoping someone could help me make a connection between the theory of isomorphism and the way it's actually applied (ex. how can we tell if two graphs are isomorphic)?

-
As you probably know, there has been a lot of work trying to find good algorithms to determine whether two graphs are isomorphic. – André Nicolas Nov 27 '12 at 7:02

Two graphs are isomorphic if and only if when someone puts you on one of them and you can walk around however you like, you can't tell which one they put you on.

Another way of expressing the same thing is that two graphs are isomorphic if they're essentially the same and differ at most in the labelling of the vertices.

-

There is one easy way to do this.
(This is the most inefficient, but most "intuitive" method to me.)
I am assuming undirected graph here, with $n$ vertices.

Suppose we were to label the graph by $1,2,\dots,n$.
As you probably know, each edge connecting vertices $i$ and $j$ can be written as $(i,j)$.
Hence we can have a sorted list of edges:
$(i_1,j_1)$
$(i_2,j_2)$
$\dots$
$(i_k,j_k)$, where $k$ is the number of edges.

Now take another graph.
If they are isomorphic, then there exists some labeling on the new graph such that the resulting sorted list of edges looks exactly the same.
So all you have to do is to go through all possible permutations of the labeling, each time round generating the edges list and comparing against the original one.
If all edges match for some labeling, then the graphs are isomorphic.
Otherwise they are not.

This method checks the structural similarity between graphs using the simplest building blocks, the edges.

This takes $n!/2$ permutations on average and hence is inefficient.
For better ways, you can do things like check if the degree sequence is the same, check number of edges or vertices same etc.

-
If degree sequences are same, number of vertices are same, number of edges are same; still the graphs may not be isomorphic. – Shahab Mar 18 '13 at 10:13
@Shahab The checks on degree sequences, order and size are suggested as negative checks. i.e. if any of these are different between the two graphs then there is certainly no isomorphism. – Yong Hao Ng Mar 24 '13 at 2:38