# Reducing from Hamiltonian Cycle to Subgraph Isomorphism

I am reading Subgraph isomorphism problem

I am having trouble understanding how they prove that the subgraph isomorphism problem is NP-Complete using the Hamiltonian cycles problem in the article.

Can someone help me explain what is happening in more laymen terms?

• I edited the title to refer to subgraph isomorphism. The graph isomorphism problem is not the same thing and whether or not there is a reduction from Hamiltonian Cycle to Graph Isomorphism is one of the biggest open questions in complexity theory. – David Richerby Dec 12 '13 at 9:20

In $\mathrm{Subgraph\,\,Isomorphism}$, you're given two graphs $G$ and $H$, and the question is whether you can delete some vertices and edges from $G$ to get $H$ (i.e. $H$ is a subgraph of $G$). The reduction from $\mathrm{Hamiltonian\,\,Cycle}$ to $\mathrm{Subgraph\,\,Isomorphism}$ is really just rephrasing what it means for a graph to have a Hamiltonian cycle.
A Hamiltonian cycle in a graph is a cycle that includes every vertex, so if we ignore the other edges in the graph, we can think of the Hamiltonian cycle as a subgraph of the original graph with the properties that it contains all the vertices, only some of the edges, and those edges make a cycle. That is, a Hamiltonian cycle in an $n$-vertex is isomorphic to the graph $C_{n}$.
So if we start with $G$ and we can find a subgraph that's isomorphic to $C_{|V(G)|}$, $G$ must be Hamiltonian. This is the same as solving the $\mathrm{Subgraph\,\,Isomorphism}$ problem where $H=C_{|V(G)|}$.