Notice that this problem is different from Graph Isomorphism: in the latter, you are given two graphsG1,G2 (presumably of the same size), and are to decide if the two are isomorphic. Graph Isomorphism is rather famous for the fact that neither is it known to be NP-complete (most researchers believe that is rather unlikely), nor does anyone have a polynomial-time algorithm. Subgraph Isomorphism, on the other hand, is known to be NP-complete, and we will prove that here.

To see that the problem is in NP, we observe that a certificate is a mapping φ from the nodes of G1 to (a subset of) the nodes of G2, describing which vertices of G2 correspond to vertices of G1. The certifier then needs to make sure that for each edge e = (u,v) in G1, the edge (φ(u),φ(v)) is also in G2, and whenever (u,v) is not an edge of G1, then (φ(u),φ(v)) is not an edge of G2. This can be done with two simple nested loops, and takes at most O(n2) time, i.e., polynomial.

To prove NP-hardness, we show that, for instance, the Clique problem is a special case. Given an instance of Clique, consisting of a graph G and a number k, we generate an instance of Subgraph Isomorphism by setting G2 = G, and G1 a clique on k vertices. This reduction clearly takes polynomial time, since all we do is copy a graph, and write down a complete graph in time O(k2).

To prove correctness of the reduction, first assume that G contains a clique of size k. Then, those k nodes of G = G2 are isomorphic to G1, because G1 is a clique of size k.

Conversely, if G2 contains a subgraph isomorphic to G1, because G1 is a k-clique, G2 must contain ak-clique. Thus, (G, k) is a “Yes” instance.