Recall that a problem is NP-complete if it is in NP and every problem in NP can be reduced to it in polynomial time. Start by showing that subgraph isomorphism is in NP by demonstrating a polynomial-time verifier for a given solution.

To prove NP-completeness, reduce a known NP-complete problem to subgraph isomorphism. Consider reducing the Clique problem (which is NP-complete) to subgraph isomorphism. Construct a transformation where the input to the Clique problem is converted into two graphs, G and H, such that G contains a clique of size k if and only if H is isomorphic to a subgraph of G.

Formalize the reduction from the Clique problem to subgraph isomorphism. For a given graph G' and integer k, construct graph G by adding a new vertex connected to all vertices of G', and construct graph H as a complete graph on k vertices. Prove that G' contains a clique of size k if and only if H is isomorphic to a subgraph of G.