Clique (graph theory)

A clique in a simple graph $G$ is a set $C$ of vertices such that every pair of distinct members is adjacent. Equivalently, its induced subgraph $G[C]$ is a complete graph. The surrounding graph need not itself be complete: a clique describes complete pairwise connectivity within a selected group.

Consider the original graph withThe set $\{a,b,c\}$ is a clique because all three pairs $ab,ac,bc$ are edges. The set $\{b,c,d\}$ is not a clique: the edge $bd$ is missing. A path in a graph connecting all selected vertices is therefore insufficient; every pair must have a direct edge.

Here the clique number is $3$. The maximum clique is $\{a,b,c\}$, but $\{c,d\}$ and $\{d,e\}$ are also maximal cliques. This distinction is useful when an algorithm stops as soon as its current clique cannot be enlarged: that stopping condition establishes maximality, while finding the largest possible clique is a separate requirement.

Given an explicitly represented finite simple graph $G$ and a nonnegative integer $k$, decide whether $G$ contains a clique of size $k$. The problem is NP-complete. A polynomial-time many-one reduction from SAT first obtains conjunctive normal form by a Tseitin transformation, makes one vertex per Boolean literal occurrence, and joins noncontradictory occurrences from different Boolean clauses. A clique as large as the Boolean clause count is equivalent to a satisfying assignment.

A maximum clique is a clique with the greatest possible number of vertices in the graph. Its size is the clique number. Every maximum clique is a maximal clique, since adding a vertex would produce a larger clique. A graph can have several maximum cliques; the word maximum specifies their common size, rather than uniqueness.

A maximal clique is a clique not strictly contained in another clique. This is distinct from a maximum clique, whose size equals the clique number. In a triangulated probabilistic graphical model, maximal cliques are the natural nodes of a junction tree.

Maximality is a condition on set inclusion: no outside vertex is adjacent to every member of the current clique. In the five-vertex example, $\{c,d\}$ is maximal because $a,b$ are not adjacent to $d$, while $e$ is not adjacent to $c$. Yet $\{a,b,c\}$ is larger. Checking every possible one-vertex extension is enough: if a larger containing clique existed, any one of its new vertices could already be added.^[ref]

An edge-disjoint clique packing is a collection of $r$-cliques no two of which share an edge; they may share vertices. Its maximum cardinality $Z_r(G)$ changes by at most one when a single edge is toggled. Removing that edge destroys at most one packed clique, which makes this variable suitable for an edge-exposure martingale.

Let $X$ count $k$-cliques in a binomial random graph on $m$ vertices and $Y$ count distinct ordered pairs sharing an edge. The clique conflict graph gives $Z_k\ge X^2/(X+Y)$: order its vertices randomly and keep each one preceding all its neighbours, then apply the Cauchy-Schwarz inequality. Another application gives $\mathbb{E}{Z}_k\ge (\mathbb{E}X{)}^2/(\mathbb{E}X+\mathbb{E}Y)$. If $\mathbb{E}Y/(\mathbb{E}X{)}^2=O(k^4/m^2)$ and $1/\mathbb{E}X$ is no larger, then $\mathbb{E}{Z}_k=\Omega (m^2/k^4)$. Changing one edge changes $Z_k$ by at most one, so the Azuma-Hoeffding inequality for an edge-exposure martingale yields the displayed exponential absence bound. This supports a union bound over exponentially many adaptive candidate subsets.

The clique conflict graph has one vertex for each $r$-clique of a fixed graph, and joins two when they share an edge. Its independent sets correspond exactly to edge-disjoint clique packings. The Caro-Wei bound converts clique-count and overlap estimates into a packing lower bound.

The clique number $\omega (G)$ is the maximum number of vertices in a clique of a finite graph:We use $\omega (G)=0$ for the graph with no vertices. For a nonempty complete graph, $\omega (K_n)=n$; for the five-vertex example, $\omega (G)=3$.

If the graph contains $K_k$ and no $K_{k+1}$ as subgraphs, its clique number is exactly $k$, because every larger clique contains a clique with $k+1$ vertices. Also $\chi (G)\ge \omega (G)$: a proper vertex coloring must assign different colors to all members of any clique. This lower bound need not be an equality; the cycle graph $C_5$ has clique number $2$ and chromatic number $3$.

A clique records pairwise relationships. If vertices represent sets and an edge means a nonempty intersection, a clique does not by itself guarantee an element common to every set. TakeThen $A\cap B=\{2\}$, $B\cap C=\{3\}$ and $C\cap A=\{1\}$, so their intersection graph is $K_3$. But $A\cap B\cap C=\varnothing$. The graph faithfully records all three pairwise intersections; the stronger claim of a single shared element requires additional hypotheses.