The definition of what it means for two graphs to be isomorphic is in homework 4.
Graph H isomorphic to a subgraph of graph G if you can obtain a graph that is isomorphic to H by removing zero or more vertices and zero or more edges from G.
The Subgraph Isomorphism Problem (SI) is as follows.
Input. Two undirected graphs G and H.
Question. Is H isomorphic to a subgraph of G?
Show that SI is in NP.
Let CP be the Clique Problem. Show that CP ≤p SI.
Are the results from the preceding two questions enough to show that SI is NP-complete, without relying on any currently unproved conjectures?
If SI has been shown to be NP-complete, can we conclude that SI is not in P without relying on any currently unproved conjectures?
... more to be added.