Clique (graph theory)

From Wikipedia, the free encyclopedia

In graph theory, a clique in an undirected graph G is a set of vertices V such that for every two vertices in V, there exists an edge connecting the two. This is equivalent to saying that the subgraph induced by V is a complete graph. The size of a clique is the number of vertices it contains.

Finding whether there is a clique of a given size in a graph (the clique problem) is NP-complete.

The opposite of a clique is an independent set, in the sense that every clique corresponds to an independent set in the complement graph.