FindClique returns a list of vertices which comprise a clique in the graph G. The optional parameter size specifies a size for the clique. If size is omitted, FindClique behaves identically to MaximumClique and returns a maximum clique.

The strategy is a branch-and-bound backtracking algorithm using the greedy color bound (see Kreher and Stinson, 1999).

For a faster algorithm that usually, but not always, returns a large clique, see GreedyClique.

$\mathrm{with}\left(\mathrm{GraphTheory}\right)\:$

$G≔\mathrm{GraphComplement}\left(\mathrm{CompleteGraph}\left(3\,4\right)\right)$

$G≔\mathrm{Graph\; 1:\; an\; undirected\; graph\; with\; 7\; vertices\; and\; 9\; edge(s)}$

$\mathrm{DrawGraph}\left(G\right)$

$\mathrm{FindClique}\left(G\,3\right)$

$\left[2\,1\,3\right]$

$\mathrm{FindClique}\left(G\,4\right)$

$\left[4\,5\,6\,7\right]$

D.L. Kreher and D.R. Stinson, Combinatorial Algorithms: Generation, Enumeration and Search, CRC Press, Boca Raton, Florida, 1998.

The GraphTheory[FindClique] command was introduced in Maple 2018.

For more information on Maple 2018 changes, see Updates in Maple 2018.