Let undirected graph G be an input to HCP that has n vertices. Let Cn by a simple cycle of n vertices. (The vertices in Cn are 1,…,n and the edges are (i, i+1) (i = 1,…,n−1) and (n,1).)
A reduction from HCP to SIP is function f given by
f(G) = (G, Cn).It should be clear that
G has a Hamilton Cycle ⇔ G has a subgraph that is isomorphic to Cn.