Bron–Kerbosch Maximal Cliques

The Bron–Kerbosch algorithm is an efficient, recursive backtracking procedure to find all maximal cliques in an undirected graph. A clique is a subset of vertices such that every two distinct vertices in the subset are adjacent. A clique is maximal if it cannot be extended by including one more adjacent vertex—meaning it is inclusion-wise unextendible. This is distinct from a maximum clique, which simply refers to the clique(s) with the largest number of vertices.

Experiment

1. Select "Triangle and tail" from the Graph dropdown.
2. Click "Step" repeatedly to trace the algorithm and see the cliques discovered.
3. Click "Finish" to jump to the final results and see the maximal clique count.

Use the interactive module below to step through the Bron–Kerbosch algorithm on various graphs. Observe how vertices transition from P (candidates) to R (the current clique) and finally to X (excluded) during backtracking. Notice that the "Edgeless" graph correctly reports individual isolated vertices as singleton maximal cliques.

Open the full module in a new tab for a dedicated view of the enumeration steps.