Réduction de la clique-6 à la clique-3

Question

Rappelez-vous que $ g $ a une clique de taille $ k $ si elle a un sous-graphique complet composé de Vertices $ k $.

Définissons le problème $ clique-k $ comme suit: $$ { langle g ring mid g text {est un graphique non dirigé qui contient une clique de taille} k } $$

---

Question: Trouvez une réduction $ f $ de $ clique-6 $ à $ clique-3 $ tel que l'entrée de $ f $ est un graphique $ g $ avec $ n $ vertices, $ f (g) $ est un graphique avec $ o (n ^ 2) $ vertices, et $$ g dans la clique-6 leftrightarrow f (g) dans la clique-3 $$

La complexité de temps requise pour le calcul de $ f $ est $ o (n ^ 4) $.

Je ne sais pas comment aborder ce problème et je serais reconnaissant si quelqu'un peut fournir des informations sur la solution.