In the Bron–Kerbosch algorithm, X keeps track of vertices already explored in the current search branch. This history prevents the search from reporting the same maximal clique again. section 11.3 section 11.1
As the search explores a vertex:
- Pass forward only vertices in X that are neighbors of the chosen vertex. section 11.1
- After the recursive call returns, move the explored vertex from P into X. section 11.1
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.
See how a nonempty X stops the branch {2, 4} from reporting a clique already found as {1, 2, 4}. section 11.1
