The Subgraph Isomorphism Problem (SIP) Input. Two undirected graphs G and H. Question. Is H isomorphic to a subgraph of G? That is, can you get a graph that is isomorphic to H by deleting zero or more edges and zero or more vertices from G? The Hamilton Cycle Problem (HCP) Input. An undirected graph G. Question. Does G contain a simple cycle that includes all of its vertices? That is, can you find a cycle in G, following the edges, that includes every vertex exactly once? (Imagine doing a tour, where you start at a particular vertex, tour through the vertices (following edges), and return to the start vertex, where you are not allowed to return to a vertex that you have already visited, except the start vertex at the end of the tour.) You showed SIP was in NPC in your homework, but we never formally did HCP. Show HPC is in NPC using SIP The Subgraph Isomorphism Problem (SIP) Input. Two undirected graphs G and H. Question. Is H isomorphic to a subgraph of G? That is, can you get a graph that is isomorphic to H by deleting zero or more edges and zero or more vertices from G? The Hamilton Cycle Problem (HCP) Input. An undirected graph G. Question. Does G contain a simple cycle that includes all of its vertices? That is, can you find a cycle in G, following the edges, that includes every vertex exactly once? (Imagine doing a tour, where you start at a particular vertex, tour through the vertices (following edges), and return to the start vertex, where you are not allowed to return to a vertex that you have already visited, except the start vertex at the end of the tour.) You showed SIP was in NPC in your homework, but we never formally did HCP. Show HPC is in NPC using SIP