The description of the subgraph isomorphism problem is as follows: Given two graphs G1 and G2, determine whether G1 is isomorphic to a subgraph of G2. First, if we obtain G1, G2, and the corresponding solution (i.e., a subgraph Gs of G2 that is isomorphic to G1), we only need to traverse the points in the solution and each edge connected to these points, checking whether they correspond to G1 to verify the correctness of the solution. Therefore, this problem is obviously an NP problem.
To prove that this problem is also an NP-hard problem, we reduce the clique problem to the subgraph isomorphism problem. Specifically, suppose we have a solvable clique problem <G, k>, where G contains k points that form a clique (i.e., these k points are mutually connected, forming a complete graph). Then we construct G1 as a complete graph with k points and construct G2 = G. Obviously, the construction of the two graphs can be completed in polynomial time.
Considering that if there is an algorithm As that can solve the subgraph isomorphism problem in polynomial time, then for a clique problem, we only need to construct G1 and G2 based on the clique problem's k and G as described above, and then give G1 and G2 to the algorithm As for the subgraph isomorphism problem. By doing so, we can determine in polynomial time whether G1 is isomorphic to a subgraph of G2, i.e., whether the complete graph with k points is contained in G, thus solving the clique problem in polynomial time.
Since we know that the clique problem is NP-complete, the aforementioned algorithm As does not exist. Therefore, the subgraph isomorphism problem is an NP-hard problem. In conclusion, the subgraph isomorphism problem is NP-complete.