The clique problem can be stated as follows: Given an undirected graph, G = (V, E), and an integer, K, does G contain a complete subgraph of at least K vertices?
The vertex cover problem can be stated as follows: Given an undirected graph, G = (V, E), and an integer, K, does G contain a subset Vt ⊂ V such that |Vt| ≤ K and every edge in G has a vertex in Vt? Show that the clique problem is polynomially reducible to vertex cover.