= Clique
{disambiguate=graph theory}
{wiki}
= Clique
{synonym}
= Complete subgraph
{synonym}
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> with
$$
V=\{a,b,c,d,e\},\qquad
E=\{ab,ac,bc,cd,de\}.
$$
The <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>.
\Image[/maximum-clique-and-maximal-edges.png]
{title=A maximum clique and a smaller maximal clique in the same graph}
{description=Left: the three highlighted <vertices> $a,b,c$ form the unique <maximum clique>. Right: the <edge> $cd$ gives a <maximal clique> of size two, because no outside <vertex> is adjacent to both endpoints. Both panels use the same original <graph>; highlighted <vertices> and <edges> select different <cliques>.}
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.
Back to article page
