Can the isomorphic graph problem be solved in deterministic polynomial time? Here is a recent homework problem of mine:


  Call graphs G and H isomorphic if the nodes of G may be reordered so
  that it is identical to H. Let ISO = {⟨G,H⟩| G and H are isomorphic
  graphs}. Show that ISO ∈ NP.


In order to solve this problem, I created a non-deterministic Turing machine that did the following:


Check if each graph has the same number of nodes
Non-deterministically arrange the edges of G in a permutation that matches H
Verify that each edge in the permutation of G matches the corresponding edge in H


As far as I know, this approach is acceptable for solving this problem with non-determinism.

My question is this: if we can compare the edges in the permutation of G against H, why can't we simply check to see if each edge in the original list of edges in G (a maximum of $n^2$ nodes) has a matching edge in H (which also has a maximum of $n^2$ nodes) for a total big O of O($n^4$)?  If this is possible, does that mean that this problem is in P?
Your approach sounds intuitively appealing on first glance, but it doesn't work.  It's not enough that each edge in $G$ has a matching edge in $H$, when taken one at a time.  There has to be a way to provide a single matching (isomorphism) that matches every edge of $G$ to a (different) edge of $H$, in a way that preserves the connectivity.

Examples:


Suppose you discover that it is possible to match edge $(a,b)$ from $G$ with edge $(u,v)$ from $H$; and you also discover that it is possible to match edge $(c,d)$ from $G$ with $(u,v)$ from $H$.  This doesn't mean there will necessarily be a way to stitch this into a complete isomorphism that describes how all vertices and edges are matched.  For instance, trying to simultaneously match both $(a,b)$ and $(c,d)$ to the same edge $(u,v)$ does not correspond to any legal graph isomorphism (different vertices have to map to different vertices, and different edges to different edges).
Suppose you discover that it is possible to match edge $(a,b)$ from $G$ with edge $(u,v)$ from $H$; and you also discover that it is possible to match edge $(b,c)$ from $G$ with $(w,x)$ from $H$, where $v \ne w$.  This doesn't mean there will necessarily be a way to stitch this into a complete isomorphism that describes how all vertices and edges are matched.  For instance, trying to simultaneously match $(a,b)$ to $(u,v)$ and $(b,c)$ to $(w,x)$ doesn't work, since you need $b$ to be consistently matched to the same vertex in both (e.g., either to $v$ both times, or to $w$ both times).


For these reasons, your approach will indeed run in polynomial time but will not compute the correct result: there will be some graphs $G,H$ where your algorithm outputs "isomorphic" but where the correct answer is "not isomorphic".



If we try to fix this problem, the naive approach is to try to find all ways to match the set of $n$ vertices in $G$ to a re-ordering of the set of vertices in $H$ (i.e., a matching that simultaneously describes what every vertex in $G$ corresponds to, in $H$).  However, there are $n!$ such candidates to try, and $n!$ is exponential in $n$, so this leads to an exponential-time algorithm.  It's a famous open problem whether the graph isomorphism problem is in P or not.  See https://en.wikipedia.org/wiki/Graph_isomorphism.