Editing Clique (graph theory) (section)

{{Short description|Adjacent subset of an undirected graph}}
{{Other uses|Clique (disambiguation)}}
[[File:VR complex.svg|thumb|upright=1.35|A graph with {{unordered list
| 23 × 1-vertex cliques (the vertices),
| 42 × 2-vertex cliques (the edges),
| 19 × 3-vertex cliques (light and dark blue triangles), and
| 2 × 4-vertex cliques (dark blue areas).}}
The 11 light blue triangles form maximal cliques. The two dark blue 4-cliques are both maximum and maximal, and the clique number of the graph is 4.]]

In [[graph theory]], a '''clique''' ({{IPAc-en|ˈ|k|l|iː|k}} or {{IPAc-en|ˈ|k|l|ɪ|k}}) is a subset of vertices of an [[undirected graph]] such that every two distinct vertices in the clique are [[Adjacent (graph theory)|adjacent]]. That is, a clique of a graph <math>G</math> is an [[induced subgraph]] of <math>G</math> that is [[complete graph|complete]]. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs. Cliques have also been studied in [[computer science]]: the task of finding whether there is a clique of a given size in a [[Graph (discrete mathematics)|graph]] (the [[clique problem]]) is [[NP-complete]], but despite this hardness result, many algorithms for finding cliques have been studied.

Although the study of [[complete graph|complete subgraphs]] goes back at least to the graph-theoretic reformulation of [[Ramsey theory]] by {{harvtxt|Erdős|Szekeres|1935}},<ref>The earlier work by {{harvtxt|Kuratowski|1930}} characterizing [[planar graph]]s by forbidden complete and [[complete bipartite graph|complete bipartite]] subgraphs was originally phrased in topological rather than graph-theoretic terms.</ref> the term ''clique'' comes from {{harvtxt|Luce|Perry|1949}}, who used complete subgraphs in [[social network]]s to model [[clique]]s of people; that is, groups of people all of whom know each other. Cliques have many other applications in the sciences and particularly in [[bioinformatics]].