A maximum clique of a graph is a clique (i.e., complete subgraph)
of maximum possible size for . Note that some authors refer to maximum cliques simply as
"cliques." The size of the maximum clique is known as a graph's clique
number, and the problem of finding the size of a clique for a given graph
is an NP-complete problem (Skiena 1997).
A maximum clique in a given graph can be found in the Wolfram
Language using FindClique[g][[1]].
The command Sort[FindClique[g,
Length /@ FindClique[g], All]] will find all maximum
cliques.
A complete k-partite graph has maximum clique size .
The largest order-
graph which does not contain the complete graph as a subgraph
is called the Turán's graph (Gross and Yellen 2006, pp. 476-477; note the
slightly nonstandard indexing by Skiena 1990, p. 218 and Pemmaraju and Skiena
2003, pp. 247-248).