A clique is a complete subgraph of some undirected graph. A clique of size is called a -clique. We define the following language
NP-Complete
Info
is NP-complete
It is known that 3SAT is -complete. A moment’s thought shows that , as we can check in polynomial time whether a subgraph is complete.
Take some 3cnf-formula with clauses
Define a graph , with nodes (unique for each clause). Start with the complete graph, and remove any edges between (within one group) and nodes with contradicting values ( and ).
If has satisfying assignment, then we have a -clique by picking a node corresponding to some true variable in each clause. None of these choices duplicate clauses or form contradiction, thus this subgraph is indeed complete.
If has a -clique, each of the nodes must be contained in some unique clause. Furthermore none of these nodes have contradicting truth values, so passing the chosen node ( or ) into and picking arbitrary values for the unused variables will give a satisfying assignment.