K₅, a complete graph. If a subgraph looks like this, the vertices in that subgraph form a clique of size 5.

A graph with 6 vertices and 7 edges. On this graph vertices 1, 2, 5 is the only clique of size 3.

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. Alternatively, a clique is a graph in which every vertex is connected to every other vertex in the graph. 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.

The term presumably comes from the idea that if the vertices represent people and the edges represent the relation 'knows', then everyone knows everyone else, thus forming a clique.

Subgraphs of a graph which are cliques may be referred to as cliques in the graph. The largest clique in a graph G is of theoretical importance and denoted ω(G).^[1]

Notes

See also

• Solving the Maximum common subgraph isomorphism problem
• Maximal clique

References

• Godsil, Chris; Gordon Royle [1949] (2004). Algebraic graph theory. New York: Springer. ISBN 0-387-95220-9.