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.
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?).