Subgraph isomorphism reduction from the Clique problem I was trying to understand the Wikipedia proof for NP-completeness of subgraph isomorphism by reduction from the clique problem. It's really just one sentence:


  Let $H$ be the complete graph $K_k$; then, the answer to the subgraph isomorphism problem for $G$ and $H$ is equal to the answer to the clique problem for $G$ and $k$.


In the subgraph isomorphism problem, $G$ and $H$ are not constrained in any way (e.g., $H$ is not constrained to complete graphs). Yet, in the proof, Wikipedia just states "let $H$ be the complete graph $K_k$". It's not defined what $K_k$ represents or why $H$ suddenly becomes constrained to a complete graph.
The decision version of the clique problem asks whether a given graph $G$ contains a complete graph with $k$ vertices as subgraph. The wikipedia article just explains why the decision version of the clique problem is a special case of the subgraph isomorphism problem. Namely if the graph $H$ is the complete graph with $k$ vertices, then the answer to this special subgraph isomorphism problem is just the answer to the decision version of the clique problem.

This shows that subgraph isomorphism is NP-hard, since the clique problem is NP-complete. But the subgraph isomorphism is obviously in NP, since it a given monomorphism from $H$ to $G$ can efficiently be checked to be a monomorphism. So we can conclude that subgraph isomorphism is NP-complete.