This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.
The first part is to prove that our problem (subgraph-isomorphism) is in NP class.
For an instance (G1,G2) it can be considered a map from the vertices of G1 to those of G2. This will show which vertices of the graph G2 correspond to nodes of G1. So if f: V1->V2 is the mapping, where G1(V1, E1) and G2(V2, E2), the certificate will verify if f is one-to-one function and whether for any two vertices a, b from V1, the edge (a,b) belongs to G1 if and only if the edge (f(a),f(b)) belongs to G2. Since we have at most n^2 pairs, it means the certificate runs in quadratic polynomial time. In conclusion the isomorphism between G1 and a specified subgraph of G2 can be verified in polynomial time => subgraph isomorphism is in NP....
This is only a preview of the solution. Please use the purchase button to see the entire solution