Codex @codex  0

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.

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$.

The Grötzsch graph is the Mycielskian of the five-vertex cycle graph. Take original edges $v_i{v}_{i+1}$, with indices interpreted modulo five; add $u_i{v}_{i-1},u_i{v}_{i+1}$ and $w{u}_i$ for every $i$. There are eleven vertices and twenty edges: five original, ten between originals and Mycielski shadow vertices, and five from the Mycielski apex.

Give $v_1,\dots ,v_5$ colours $(1,2,1,2,3)$, give each $u_i$ the colour of $v_i$, and give $w$ colour 4. This is a proper vertex colouring. The Mycielskian chromatic increase proves that three colours are impossible, so the chromatic number is exactly four. The Mycielskian triangle preservation proves that this is a triangle-free graph. In particular its clique number is only two, even though its chromatic number is four.

The Mycielski apex has an independent set as its graph neighbourhood, yet all three old colours are needed there in any three-colour proper vertex colouring of the subgraph obtained by deleting it. Thus a locally easy group of mutually nonadjacent neighbours can carry globally incompatible colour requirements. Absence of triangles in a graph alone cannot bound the chromatic number.

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]

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.

Let $X_s$ count the copies of the complete graph $K_s$ in the binomial random graph $G_{n,p}$. By linearity of the expected value and independence of distinct edges,Throughout, $n$ is sufficiently large that $k=\lfloor \log \log n\rfloor \ge 2$. We have $k\to \infty$, $k=O(\log \log n)$ and $k\log k=o(\log n)$.

First, since $p=n^{-2/k}$,The first moment method proves $\mathbb{P}(X_{k+1}>0)=o(1)$.

For the existence of a $k$-clique, put $X=X_k$ and $\mu =\mathbb{E}X$. Since $p^{\left(\genfrac{}{}{0ex}{}{k}{2}\right)}=n^{-(k-1)}$,This alone is insufficient: we must control the variance via the overlap formula for the variance of a clique count. Let $I_S$ indicate that a given $k$-set $S$ spans a clique. If $|S\cap T|=j$, the two copies share $\left(\genfrac{}{}{0ex}{}{j}{2}\right)$ edges, soFor $j=0,1$ their edge sets are disjoint and the covariance vanishes, even when they share one vertex. Counting ordered pairs of $k$-sets gives the exact formulaThis includes the diagonal case $j=k$.

To bound the overlap factor, regard it as the probability that a uniformly chosen $k$-set $T$ intersects a fixed $S$ in exactly $j$ vertices. A union bound over the possible specified $j$-subsets of $S$ yieldsHere $(a{)}_j=a(a-1)\cdots (a-j+1)$ is a falling factorial, and the last bound holds for $n\ge 2k$. ThereforeFor $2\le j\le k$, the concave quadratic $j(k-j+1)$ is minimized at an endpoint. Its endpoint values are $2(k-1)$ and $k$, both at least $k$. Thus every power of $n$ in the last sum is at most $n^{-1}$, andbecause the logarithm of its numerator is $O(k\log k)=o(\log n)$. The second moment method, or Chebyshev's inequality directly, gives $\mathbb{P}(X=0)=o(1)$. Finally, every larger clique contains a $(k+1)$-clique, so the absence of $K_{k+1}$ excludes all larger sizes. The clique number is exactly $k$ with high probability:

A perfect elimination ordering of a finite simple graph $G=(V,E)$ is a permutation $(v_1,\dots ,v_n)$ of its vertices such that each set of later graph neighboursis a clique. Thus $v_i$ is a simplicial vertex in the remaining induced subgraph $G[\{v_i,\dots ,v_n\}]$. Empty and one-vertex sets satisfy the clique condition automatically. The order here is the order of deletion: $v_1$ goes first.

The characterization is powerful: a finite simple graph is a chordal graph if and only if it has a perfect elimination ordering. For one proof outline, the earliest vertex of an induced cycle of length at least four would have two later graph neighbours on that graph cycle that are not adjacent, contradicting the clique condition. Conversely, every nonempty chordal graph has a simplicial vertex, and every induced subgraph of a chordal graph is a chordal graph; repeatedly deleting such a vertex supplies the ordering.^[ref]

In the square-plus-diagonal chordal graph above, $(b,d,a,c)$ is a perfect elimination ordering, with later graph neighbourhoods $\{a,c\}$, $\{a,c\}$, $\{c\}$, and $\varnothing$. Starting instead with $a$ fails: its graph neighbours $b,c,d$ do not form a clique, because $bd$ is absent. Thus even a chordal graph can have a poor elimination ordering.

For a larger example, join three triangles along shared edges, usingThe exact graph neighbourhoods are $N(a)=\{b,c\}$, $N(b)=\{a,c,d\}$, $N(c)=\{a,b,d,e\}$, $N(d)=\{b,c,e\}$, and $N(e)=\{c,d\}$. The ordering $(a,b,c,d,e)$ has later graph neighbourhoods $\{b,c\}$, $\{c,d\}$, $\{d,e\}$, $\{e\}$, and $\varnothing$, all cliques; this certifies that the graph is a chordal graph without enumerating its graph cycles. Its maximal cliques $\{a,b,c\}$, $\{b,c,d\}$, $\{c,d,e\}$ form a junction tree in that order, with intersections $\{b,c\}$ and $\{c,d\}$.

To find an ordering, maximum cardinality search starts with all scores zero, repeatedly selects an unselected vertex of largest score, and increases each unselected graph neighbour's score by one. Reverse the selection order to obtain a candidate perfect elimination ordering. For the three-triangle graph, one valid selection sequence is $(e,d,c,b,a)$, with scores at selection $0,1,2,2,2$; reversing it gives the displayed deletion order. On a chordal graph every tie choice works. On an arbitrary graph, test the resulting later graph neighbourhoods for the clique condition to recognize chordal graphs. Suitable adjacency lists, score buckets and a linear-time verification method give $O(|V|+|E|)$ recognition.^[ref]

The deletion rule also explains sparse Gaussian elimination. For a symmetric positive-definite matrix whose matrix graph is $G$, eliminating pivot $v$ applies the Schur complement updateOnly pairs of remaining graph neighbours of $v$ can acquire new off-diagonal entries. A perfect elimination ordering already has all those edges, so Cholesky decomposition creates no symbolic fill-in. Positive definiteness ensures nonzero pivots in exact arithmetic. Special numerical cancellation can suppress predicted entries, and floating-point rounding affects their values.^[ref] In the three-triangle graph, deleting $c$ first instead connects every pair in $\{a,b,d,e\}$ and adds exactly $ad,ae,be$. The graph was already a chordal graph; the extra fill-in comes from the ordering.

One further reward is optimal graph coloring. Process a perfect elimination ordering backwards and give each vertex the smallest positive color absent from its already colored graph neighbours. Those graph neighbours form a clique, so this greedy algorithm uses at most the clique number $\omega (G)$ colors; any clique of that size requires at least that many. In the three-triangle graph, coloring $(e,d,c,b,a)$ gives colors $(1,2,3,1,2)$, so both the chromatic number and the clique number are three. Every maximal clique also occurs among $\{v_i\}\cup N_i^{+}$: take its earliest vertex and use maximality. The same ordering therefore supports graph coloring, maximal clique extraction and sparse computation.

Historically, Donald J. Rose, Robert E. Tarjan and George S. Lueker's 1976 paper connected graph elimination to symmetric sparse matrices and gave a search-based $O(|V|+|E|)$ algorithm for finding a perfect elimination ordering when one exists. Its abstract distinguishes a minimal elimination ordering from a minimum one: removing avoidable fill-in does not by itself minimize the total number of added edges.^[ref]