Suppose you want to find groups of users in which everyone is directly connected to everyone else. Each such group is a clique. A maximal clique goes one step further: no additional vertex can join without breaking that all-to-all connection. “Maximal” does not mean “largest in the graph.” It means the group cannot be extended. section 11.1
Why a connected pair may not be an answer
In the example graph, {1, 2, 4} is a maximal clique. Although {2, 4} is also a clique, vertex 1 can join it, so {2, 4} is not maximal. Another maximal clique, {2, 3, 5}, overlaps the first at vertex 2. The task is to find every group that cannot grow, not just one large group. section 11.1
Bron–Kerbosch finds these groups by growing a clique and backtracking when a branch is finished:
- Keep three sets: R is the clique under construction, P holds vertices still eligible to join, and X holds vertices already explored. section 11.1
- Choose a vertex from P and add it to R. Intersect P and X with that vertex’s neighbors so the next branch retains only compatible vertices. section 11.1
- Report R only when both P and X are empty. If P is empty but X is not, do not report it: an earlier branch already accounted for a larger clique. section 11.4
Figure 11.5 A branch that closes without producing a new clique. Extending R to {2, 4} empties P, but X still holds vertex 1. A non-empty X at this point means {2, 4} is only a subset of a clique already found on an earlier branch ({1, 2, 4}) so the recursion backtracks here without reporting anything.
Follow the branch ending at {2, 4}: P is empty, but vertex 1 remains in X. That single excluded vertex shows why the branch must not produce another answer. section 11.1
Checking every subset by brute force becomes impractical as the graph grows. Bron–Kerbosch narrows each branch with neighbor intersections; a pivot can reduce branching further by limiting which candidates are tried. Maximal-clique finding also applies beyond social groups: in stereo vision, a compatibility graph connects candidate feature matches that can coexist, letting a search identify mutually consistent groups of matches. section 11.4 section 11.2
