Consider the following problem:  Given two graphs $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$ and some non-negative integer $k \in \mathbb{N}$, is it possible to delete at most $k$ vertices from $G_1$ to obtain $G_1'$ such that $G_1' \cong G_2$, i.e. the resulting graph is isomorphic to $G_2$.I have to show that this problem is NP-complete.Can somebody help me with this problem? It is school homework and I don't know how to solve it.
How to prove this isomorphism-related graph problem is NP-complete?
complexity theory;np complete;reductions