Efficient graph isomorphism for similar graph queries
This is a simple polynomial time reduction to show that the problem is GI complete: even if you know that $G_1, G_2$ are isomorphic, checking if $G_3$, built from $G_2$ deleting and adding a node, is isomorphic to $G_1$ is as hard as graph isomorphism itself (in the worst case).

Given two graphs $G = (V, E), G'= (V', E')$ build 

$G_1 = ( V \cup V' \cup \{u\},\; E \cup E' \cup \{ (v_i,u) \mid v_i \in V \})$

i.e. the union of the two graphs plus an extra node $u$ connected to all the vertices of $V$

pick $G_2 = G_1$; and clearly they are isomorphic.

Now build $G_3$ deleting $u$ and adding $u'$ connected to all the vertices of $V'$:

$G_3 = ( V \cup V' \cup \{u'\},\; E \cup E' \cup \{ (v_i',u') \mid v_i' \in V'\} )$

$G_1, G_3$ are isomorphic iff $G, G'$ are isomorphic.