In

graph analysis and

graph theory, a k-clique is a group of k

nodes, where each node in the

clique is connected to every other node in the clique. The k-clique problem at the present is in

class NP, which means that there is no solution to finding cliques in

polynomial time, but if a clique is found in the graph, it can be verified in polynomial time. The

Turing Machine described below can verify the k-clique in polynomial time.

TM KClique = "on input <

*G* ,

*k* >, where

*G* is a graph:

1: Nondeterministically select a set of nodes

*k* nodes from

*G* .

2: Test if

*G* contains all edges connecting the nodes in set

*k* .

3: If all nodes in

*k* are connected,

*accept*, else

*reject*.

From

Michael Sipser's book

Introduction to the Theory of Computation.