Une clique est un sous-ensemble de sommets d'un graphe qui sont tous adjacents deux à deux : il existe une arête entre chaque paire de sommets du sous-ensemble. Autrement dit, c'est un sous-graphe complet. Le problème du clique maximum (max clique) consiste à trouver la taille de la plus grande clique d'un graphe donné, ou à identifier les sommets qui la composent.
Un sous-ensemble S de k sommets est une clique lorsque les k(k−1)/2 paires possibles sont toutes des arêtes du graphe — aucune exception. Le panneau de droite compare en permanence le nombre de paires nécessaires à celui des paires réellement présentes ; l'écart entre les deux, affiché en rouge, tombe à zéro exactement quand S est une clique. Les paires manquantes sont tracées en pointillé rouge sur le graphe pour qu'on voie immédiatement ce qui empêche S d'être une clique complète.
Le préréglage 6, à l'inverse, cache une clique de taille 4 au milieu d'arêtes de bruit disposées pour brouiller la lecture visuelle — la force brute la retrouve en un instant, quelle que soit la disposition des sommets à l'écran, puisqu'elle ne regarde que la matrice d'adjacence.
Une clique de G — tous les sommets choisis pairwise adjacents — devient, vue dans le graphe complémentaire Ḡ (où l'on relie exactement les paires qui n'étaient pas reliées dans G), un ensemble indépendant : aucun des sommets choisis n'y est adjacent à un autre. La plus grande clique de G a donc exactement la taille du plus grand ensemble indépendant de Ḡ : ω(G) = α(Ḡ). Le panneau numérique calcule les deux quantités par deux algorithmes de force brute entièrement indépendants — l'un cherchant des paires toutes présentes, l'autre des paires toutes absentes — et affiche l'écart, qui doit rester rigoureusement nul.
L'énumération par force brute des planches précédentes teste les 2ⁿ sous-ensembles un par un — praticable jusqu'à une vingtaine de sommets, ingérable au-delà. L'algorithme de Bron et Kerbosch (1973) énumère exactement les mêmes cliques maximales, mais en construisant R sommet par sommet et en coupant aussitôt les branches condamnées : P contient les candidats qui pourraient encore rejoindre R, X ceux qu'on a déjà essayés dans cette branche et qu'il est donc inutile de retenter. Quand P et X sont tous deux vides, R est une clique maximale.
Le graphe de Turán T(n,r) répartit les n sommets en r parts aussi égales que possible et relie deux sommets si et seulement s'ils appartiennent à des parts différentes : c'est un graphe r-parti complet, sans aucune arête à l'intérieur d'une part. Sa plus grande clique vaut exactement r — on ne peut prendre qu'un sommet par part sous peine de retomber sur une paire non reliée — et le panneau confirme ω = r par l'algorithme de Bron–Kerbosch à chaque réglage de n et r.
Imaginons une fête où chaque paire d'invités est soit déjà amie, soit inconnue l'une de l'autre. Représentons les invités par les sommets d'un graphe complet, et colorions chaque arête en rouge (amis) ou bleu (inconnus). Un « trio homogène » — trois invités mutuellement amis, ou mutuellement inconnus — est exactement une clique de taille 3 dans l'un des deux sous-graphes monochromes. Combien faut-il d'invités pour garantir un tel trio, quelle que soit la façon de colorier les arêtes ?
La réponse est le nombre de Ramsey R(3,3) = 6, et la page le vérifie ici par force brute plutôt que de l'énoncer : sur K₅, l'énumération complète des 2¹⁰ = 1024 coloriages possibles en retrouve 12 qui échappent à tout triangle monochrome — dont le « pentagone » (un cycle rouge à cinq côtés, son complémentaire bleu) affiché par le bouton témoin. Sur K₆, l'énumération complète des 2¹⁵ = 32768 coloriages ne trouve, sans une seule exception, aucun coloriage capable d'éviter le trio homogène.