# Reduction from Clique-6 to Clique-3

Recall that $G$ has a clique of size $k$ if it has a complete sub graph consisting of $k$ vertices.

Let us define the problem $Clique-k$ as follows: $$\{ \langle G \rangle \mid G \text{ is an undirected graph that contains a clique of size } k\}$$

Question: Find a reduction $f$ from $Clique-6$ to $Clique-3$ such that $f$'s input is a graph $G$ with $n$ vertices, $f(G)$ is a graph with $O(n^2)$ vertices, and $$G \in Clique-6 \Leftrightarrow f(G) \in Clique-3$$

The required time complexity for the computation of $f$ is $O(n^4)$.

I am not sure how to approach this problem, and would be thankful if someone can provide insights \ directions to the solution.

## 1 Answer

Create a new graph whose vertices are pairs of vertices in the original graph (optimization: 2-cliques, i.e. edges, in the original graph), and whose edges correspond to 4-cliques. The new graph has a 3-clique iff the original graph has a 6-clique (why?).

• I was trying to do just that but instead of creating vertices from edges, I created them from triangles (3-cliques) so it did not work. This really helped a lot, thank you! – Phil Spencer Jun 21 '17 at 17:06