Prouver que «presque la clique» est complète np

Question

Étant donné $ g = (v, e) $, graphique non dirigé, un groupe de sommets $ s $ est appelé presque clique Si en ajoutant un seul bord, $ s $ devient une clique.

Considérez la langue: $ l = { langle g, t rangle mid text {le graphique (g ) contient a (t ) - presque clique} } $. Prouvez que $ l $ est NP-complete.

De toute évidence, il est résolu par la réduction polynomiale, mais est-ce de la clique ou du 3SAT? Et comment?