Recall that if G$1$ and G$2$ are graphs, a graph isomorphsim is a bijective function f : V $($G$1)->$

V $($G$2)$ such that u $$ v in G$1$ if and only if f$($u$)$ f$($v$)$ in G$2.$ In other words, f is a bijection

that maps adjacent vertices to adjacent vertices and non$-$adjacent vertices to non$-$adjacent

vertices.

The subgraph$-$isomorphism problem takes two undirected graphs G$1$ and G$2,$ and it asks

whether G$1$ is isomorphic to a subgraph of G$2.$ Formally, we define

SUBGRAPH$-$ISO $=\{$G$1,$ G$2|$H $$ G$2,$ f : V $($G$1)->$ V $($H$)$ such that f is an isomorphism$\}$

Show that SUBGRAPH$-$ISO is NP$-$complete.