Clique (graph theory)

In <a href="/facts/Graph_theory/VVPCd4TX">graph theory</a>, a clique is a subset of vertices of an <a href="/facts/Undirected_graph/kw3eIBUe">undirected graph</a> such that every two distinct vertices in the clique are <a href="/facts/Adjacent_(graph_theory)/W0MqKkyE">adjacent</a>. That is, a clique of a graph 
 
 
 
 G
 
 
 {\displaystyle G}
 
 is an <a href="/facts/Induced_subgraph/G3EUC0MQ">induced subgraph</a> of 
 
 
 
 G
 
 
 {\displaystyle G}
 
 that is <a href="/facts/Complete_graph/AYD6hUqI">complete</a>. 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 <a href="/facts/Computer_science/lN3pEyPz">computer science</a>: the task of finding whether there is a clique of a given size in a <a href="/facts/Graph_(discrete_mathematics)/kw3eIBUe">graph</a> (the <a href="/facts/Clique_problem/cVVBNP08">clique problem</a>) is <a href="/facts/NP-complete/NFPv56DU">NP-complete</a>, but despite this hardness result, many algorithms for finding cliques have been studied.
Although the study of <a href="/facts/Complete_graph/AYD6hUqI">complete subgraphs</a> goes back at least to the graph-theoretic reformulation of <a href="/facts/Ramsey_theory/CzLLM2j8">Ramsey theory</a> by Erdős & Szekeres (1935), the term clique comes from Luce & Perry (1949), who used complete subgraphs in <a href="/facts/Social_network/kQg6aEVf">social networks</a> to model <a href="/facts/Clique/udmBpXLC">cliques</a> of people; that is, groups of people all of whom know each other. Cliques have many other applications in the sciences and particularly in <a href="/facts/Bioinformatics/D5x2L8ee">bioinformatics</a>.

Clique (graph theory) open-in-new

Clique (graph theory)