How to prove this isomorphism-related graph problem is NP-complete?
Here's a hint:  Consider Vertex Cover, which is NP-complete.  If $G = (V,E)$ has a vertex cover of size $k$, then you can remove $k$ vertices from $G$ to obtain $G'$ such that $G'$ is an edgeless graph on $n-k$ vertices.

Edit:  The correct reduction (by using Vertex Cover) shows the problem to be NP-hard.  Given the correct witnesses, you can easily show that it is in NP.