Imagine looking for groups in a network where everyone is connected to everyone else. Trying every possible group quickly becomes impractical: 50 vertices have more than a quadrillion subsets. Recursion offers a way to explore one possible group, extend it with a compatible vertex, and then return to try another path. The Bron–Kerbosch algorithm uses this recursive backtracking to find maximal cliques. section 11.1
Each call carries three sets:
- R is the clique built so far; every vertex in it connects to every other vertex in it. section 11.1
- P contains vertices still eligible to join R. section 11.1
- X records vertices already explored, preventing the same maximal clique from being reported again. section 11.1
Start with R and X empty and every vertex in P. Choose a vertex from P, add it to R, and make a recursive call. In that call, intersect P and X with the chosen vertex’s neighbors: only vertices compatible with the growing clique carry forward. When both P and X are empty, report R as a maximal clique. After a call returns, move its chosen vertex from P to X and try the next branch. An empty P alone is not enough: a vertex in X may show that R belongs to a clique already found. section 11.1
Follow one branch
On a small network, successive calls add vertices 1, 2, and 4 to R. Neighbor intersections narrow P until P and X are both empty, yielding maximal clique {1, 2, 4}. The calls then unwind so the search can explore other branches; one later branch finds {2, 3, 5}. section 11.1
Figure 11.3 Recursive trace of Branch 1 on the full network. The algorithm progressively locks nodes 1, 2, and 4 into R, pruning prospective candidates in P via neighbor intersections until both P and X are empty, confirming maximal clique {1, 2, 4}.
Trace how each recursive call grows R while neighbor intersections shrink the remaining candidates. section 11.1
Why does returning to an earlier branch work? Function calls use a last-in, first-out stack: a call finishes before control returns to the call that made it. Calls that keep stacking without finishing can cause stack overflow. Recursion is therefore more than repeating a function call; the search needs conditions that let branches finish. section 1.4.3 section 11.1
























