Can we intuitively say 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)?
 A: 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.
A: 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.
