outer call to the algorithm, it is not a neighbor of v and is excluded from the subset of X passed to the recursive call). This recursive call will end up making three second-level recursive calls to the algorithm that report the three cliques {3,4}, {4,5}, and {4,6}. Then, vertex 4 is added to X and removed from P. In the third and final iteration of the inner loop of the algorithm, for v = 6, there is a recursive call to the algorithm with R = {6}, P = Ø, and X = {4}. Because this recursive call has P empty and X non-empty, it immediately backtracks without reporting any more cliques, as there can be no maximal clique that includes vertex 6 and excludes vertex 4. The call tree for the algorithm, therefore, looks like: BronKerbosch2(Ø, {1,2,3,4,5,6}, Ø) BronKerbosch2({2}, {1,3,5}, Ø) BronKerbosch2({2,3}, Ø, Ø): output {2, 3} BronKerbosch2({2,5}, {1}, Ø) BronKerbosch2({1,2,5}, Ø, Ø): output {1,2,5} BronKerbosch2({4}, {3,5,6}, Ø) BronKerbosch2({3,4}, Ø, Ø): output {3,4} BronKerbosch2({4,5}, Ø, Ø): output {4,5} BronKerbosch2({4,6}, Ø, Ø): output {4,6} BronKerbosch2({6}, Ø, {4}): no output The graph in the example has degeneracy two; one possible degeneracy ordering is 6,4,3,1,2,5. If the vertex-ordering version of the Bron–Kerbosch algorithm is applied to the vertices, in this order, the call tree looks like BronKerbosch3(G) BronKerbosch2({6}, {4}, Ø) BronKerbosch2({6,4}, Ø, Ø): output {6,4} BronKerbosch2({4}, {3,5}, {6}) BronKerbosch2({4,3}, Ø, Ø): output {4,3} BronKerbosch2({4,5}, Ø, Ø): output {4,5} BronKerbosch2({3}, {2}, {4}) BronKerbosch2({3,2}, Ø, Ø): output {3,2} BronKerbosch2({1}, {2,5}, Ø) BronKerbosch2({1,2}, {5}, Ø) BronKerbosch2({1,2,5}, Ø, Ø): output {1,2,5} BronKerbosch2({2}, {5}, {1,3}): no output BronKerbosch2({5}, Ø, {1,2,4}): no output Worst-case analysis The Bron–Kerbosch algorithm is not an output-sensitive algorithm: unlike some other algorithms for the clique problem, it does not run in polynomial time per maximal clique generated. However, it is efficient in a worst-case sense: by a result of , any n-vertex graph has at most 3n/3 maximal cliques, and the worst-case running time of the Bron–Kerbosch algorithm (with a pivot strategy that minimizes the number of recursive calls made at each step) is O(3n/3), matching this bound. For sparse graphs, tighter bounds are possible. In particular the vertex-ordering version of the Bron–Kerbosch algorithm can be made to run in time , where is the degeneracy of the graph, a measure of its sparseness. There exist -degenerate graphs for which the total number of maximal cliques is , so this bound is