Clique (graph theory)

From Wikipedia, the free encyclopedia

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

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. A maximal clique is a clique to which no more vertices can be added.

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.

[edit] See also

• Clique problem
• Solving the Maximum common subgraph isomorphism problem