Suppose the number of vertices in $H$ is $r$. To show this problem is in $NP$, we guess a subset of $r$ vertices of $G$ and we also guess a mapping (that is, a matching) of the vertices in $H$ to the chosen vertices in $G$. Then, in polynomial time we can check that every edge of $H$ has a corresponding edge in $G$. \par To see that \textsc {Subgraph-Isomorphism} is {\NP }-hard, we will reduce the Hamiltonian cycle problem to this one. In particular, given an instance $G=(V,E)$ of the Hamiltonian cycle problem, we define a subgraph $H$ to be a simple cycle of $|V|$ vertices. This graph $H$ is a subgraph of $G$ if and only if $G$ is Hamiltonian. This reduction clearly takes polynomial time.