Maximal clique

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]