# How to prove this isomorphism-related graph problem is NP-complete?

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.

## migrated from cstheory.stackexchange.comJan 16 '13 at 15:37

This question came from our site for theoretical computer scientists and researchers in related fields.

• What have you tried? Do you know how one usually proves that a problem is NP-complete? – Yuval Filmus Jan 16 '13 at 13:08
• I have to find another NP-complete problem and reduce it to this one, but I cannot think of a way to transform this problem into another problem. – Charlie Jan 16 '13 at 13:11
• Good thing you don't have to: you have to transform instances of the other problem into ones of this problem. – Raphael Jan 16 '13 at 15:48

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.