Subgraph isomorphism

In theoretical computer science, the subgraph isomorphism problem is a computational task in which two graphs G and H are given as input, and one must determine whether G contains a subgraph that is isomorphic to H. Subgraph isomorphism is a generalization of both the maximum clique problem and the problem of testing whether a graph contains a Hamiltonian cycle, and is therefore NP-complete. However certain other cases of subgraph isomorphism may be solved in polynomial time.

Sometimes the name subgraph matching is also used for the same problem. This name puts emphasis on finding such a subgraph as opposed to the bare decision problem.

To prove subgraph isomorphism is NP-complete, it must be formulated as a decision problem. The input to the decision problem is a pair of graphs G and H. The answer to the problem is positive if H is isomorphic to a subgraph of G, and negative otherwise.

Formal question:

Let ${\displaystyle G=(V,E)}$, ${\displaystyle H=(V^{\prime },E^{\prime })}$ be graphs. Is there a subgraph ${\displaystyle G_{0}=(V_{0},E_{0}):V_{0}\subseteq V,E_{0}\subseteq E\cap (V_{0}\times V_{0})}$ such that ${\displaystyle G_{0}\cong H}$? I.e., does there exist an ${\displaystyle f\colon V_{0}\rightarrow V^{\prime }}$ such that ${\displaystyle (v_{1},v_{2})\in E_{0}\Leftrightarrow (f(v_{1}),f(v_{2}))\in E^{\prime }}$?

...
Wikipedia