Editing Clique (graph theory) (section)

==Mathematics==
Mathematical results concerning cliques include the following.
* [[Turán's theorem]] gives a [[lower bound]] on the size of a clique in [[dense graph]]s.{{sfnp|Turán|1941}}  If a graph has sufficiently many edges, it must contain a large clique. For instance, every graph with <math>n</math> vertices and more than <math>\scriptstyle \left\lfloor\frac{n}{2}\right\rfloor \cdot \left\lceil\frac{n}{2}\right\rceil</math> edges must contain a three-vertex clique.
* [[Ramsey's theorem]] states that every graph or its [[complement graph]] contains a clique with at least a logarithmic number of vertices.{{sfnp|Graham|Rothschild|Spencer|1990}}
* According to a result of {{harvtxt|Moon|Moser|1965}}, a graph with 3''n'' vertices can have at most 3<sup>''n''</sup> maximal cliques. The graphs meeting this bound are the Moon–Moser graphs ''K''<sub>3,3,...</sub>, a special case of the [[Turán graph]]s arising as the extremal cases in Turán's theorem.
* [[Hadwiger conjecture (graph theory)|Hadwiger's conjecture]], still unproven, relates the size of the largest clique [[graph minor|minor]] in a graph (its [[Hadwiger number]]) to its [[chromatic number]].
* The [[Erdős–Faber–Lovász conjecture]] relates graph coloring to cliques.
* The [[Erdős–Hajnal conjecture]] states that families of graphs defined by [[forbidden graph characterization]] have either large cliques or large [[Coclique|cocliques]]. 

Several important classes of graphs may be defined or characterized by their cliques:
* A [[cluster graph]] is a graph whose [[connected component (graph theory)|connected components]] are cliques.
* A [[block graph]] is a graph whose [[biconnected component]]s are cliques.
* A [[chordal graph]] is a graph whose vertices can be ordered into a perfect elimination ordering, an ordering such that the [[neighborhood (graph theory)|neighbors]] of each vertex ''v'' that come later than ''v'' in the ordering form a clique.
* A [[cograph]] is a graph all of whose induced subgraphs have the property that any maximal clique intersects any [[maximal independent set]] in a single vertex.
* An [[interval graph]] is a graph whose maximal cliques can be ordered in such a way that, for each vertex ''v'', the cliques containing ''v'' are consecutive in the ordering.
* A [[line graph]] is a graph whose edges can be covered by edge-disjoint cliques in such a way that each vertex belongs to exactly two of the cliques in the cover.
* A [[perfect graph]] is a graph in which the clique number equals the [[chromatic number]] in every [[induced subgraph]].
* A [[split graph]] is a graph in which some clique contains at least one endpoint of every edge.
* A [[triangle-free graph]] is a graph that has no cliques other than its vertices and edges.

Additionally, many other mathematical constructions involve cliques in graphs. Among them,
* The [[clique complex]] of a graph ''G'' is an [[abstract simplicial complex]] ''X''(''G'') with a simplex for every clique in ''G''
* A [[simplex graph]] is an undirected graph κ(''G'') with a vertex for every clique in a graph ''G'' and an edge connecting two cliques that differ by a single vertex. It is an example of [[median graph]], and is associated with a [[median algebra]] on the cliques of a graph: the median ''m''(''A'',''B'',''C'') of three cliques ''A'', ''B'', and ''C'' is the clique whose vertices belong to at least two of the cliques ''A'', ''B'', and ''C''.<ref>{{harvtxt|Barthélemy|Leclerc|Monjardet|1986}}, page 200.</ref>
* The [[clique-sum]] is a method for combining two graphs by merging them along a shared clique.
* [[Clique-width]] is a notion of the complexity of a graph in terms of the minimum number of distinct vertex labels needed to build up the graph from disjoint unions, relabeling operations, and operations that connect all pairs of vertices with given labels. The graphs with clique-width one are exactly the disjoint unions of cliques.
* The [[Intersection number (graph theory)|intersection number]] of a graph is the minimum number of cliques needed to cover all the graph's edges.
* The [[clique graph]] of a graph is the [[intersection graph]] of its maximal cliques.

Closely related concepts to complete subgraphs are [[subdivision (graph theory)|subdivision]]s of complete graphs and complete [[graph minor]]s. In particular, [[Kuratowski's theorem]] and [[Wagner's theorem]] characterize [[planar graph]]s by forbidden complete and [[complete bipartite graph|complete bipartite]] subdivisions and minors, respectively.