Reducing from Hamiltonian Cycle to Subgraph Isomorphism

Problem Detail: 

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?

Asked By : CowZow

Answered By : Luke Mathieson

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)|}$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/18906