Subgraph isomorphism
We have the graphs $G_1=(V_1,E_1), G_2=(V_2,E_2)$.
Question: Is the graph G_1 isomorphic with a subgraph of $G_2$ ?
(i.e. is there a subset of vertices of $G_2, V \subseteq V_2$ and subset of the edges of $G_2 E \subseteq E_2$ such that $|V|=|V_1|$ and $|E|=|E_1|$ and is there a one-to-one matching of the vertices of $G_1$ at the subset of vertices $V$ of $G_2 f:V_1 \to V$ such that $\{u,v\} \in E_1 \Leftrightarrow \{ f(u),f(v) \} \in E$)
In order to show that the problem is in NP, could we say the following?
A non-deterministic Turing machine can first "guess" which subgraph $G$ of $G_2$ is isomorphic with $G_1$ and then verify that $G$ is isomorphic with $G$ in $O(V_1+E_1)$ steps, since if we assume that the graphs are represented as adjacency lists, $G_1$ will have $O(V_1+E_1)$ elements.
Or could I improve something?
I want to show that the problem is NP-complete, reducing the clique problem to it (Hint: assume that the graph $G_1$ is complete)
Could you give me a hint how we could reduce the clique problem to our problem in order to show that the latter is NP-complete?