# Generalization of Subgraph Isomorphism

I am wondering how to prove that Subgraph Isomorphism is NP Complete. Wikipedia indicates that the CLIQUE problem can be used to demonstrate this, but I can't figure out how. I also found this link that demonstrates how Subgraph Isomorphism reduces to CLIQUE, but I can't figure out how to reverse it. Subgraph isomorphism reduction from the Clique problem

Here is a formal example of the problem from DASGUPTA 8.10: Given as input two undirected graphs G and H, determine whether G is a subgraph of H (that is, whether by deleting certain vertices and edges of H we obtain a graph that is, up to renaming of vertices, identical to G), and if so, return the corresponding mapping of V (G) into V (H).

• Well, what happens if you choose $G$ to be a clique with $k$ vertices? – dkaeae Mar 11 '19 at 16:18
• Can you do that? If so, that is the answer because a clique will contain every possible subgraph of size k. But is it legal to constrain the input to a specific G that is fully connected? I thought it had to take any graphs G and H – DanGoodrick Mar 11 '19 at 16:20
• The question you link actually shows that clique reduces to subgraph isomorphism, which is the exact thing you're looking for. – David Richerby Mar 11 '19 at 16:35
• Possible duplicate of Subgraph isomorphism reduction from the Clique problem – David Richerby Mar 11 '19 at 16:35
• The link I provided assumes a fully connected graph but my question only specifies any graph H. Is the reduction still possible/valid in this case? – DanGoodrick Mar 13 '19 at 12:01

• We're trying to reduce $k$-clique to sub graph isomorphism. That means we're given a graph $F$ and a number $k$, and we need to produce graphs $G$ and $H$ such that $G$ has a subgraph isomorphic to $H$ if, and only if, $F$ has a clique of size at least $k$. We get to choose the input to subgraph isomorphism. – David Richerby Mar 13 '19 at 12:42