= 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.<Graph Theory by Reinhard Diestel>[§1.1, printed p. 4 of the third electronic edition (2005): maximal sets refer to inclusion]{ref}
Back to article page
