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. 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]