A clique of a finite simple graph 
is a subgraph
of 
that is a complete
graph, and the clique of largest possible size is referred to as a maximum
clique (which has size known as the (upper) clique
number 
). However, care is needed since maximum
cliques are often called simply "cliques" (e.g., Harary 1994). A maximal clique is a clique that cannot be extended
by including another graph vertex adjacent
to every graph vertex already in the clique, meaning
it is not a subset of a larger clique. Maximum
cliques are therefore maximal cliques (but
not necessarily vice versa).
Cliques arise in a number of areas of graph theory and combinatorics, including graph coloring and the theory of error-correcting codes.
A clique of size 
is called a 
-clique
(though this term is also sometimes used to mean a maximal
set of vertices that are at a graph
distance no greater than 
from each other). 0-cliques correspond to the empty set
(sets of 0 vertices), 1-cliques
correspond to vertices, 2-cliques to edges,
and 3-cliques to 3-cycles.
The clique polynomial of a graph 
is defined as
 |
where 
is the number of cliques of size 
, with 
, 
equal to the vertex count
of 
, 
equal to the edge count of 
,
etc.
In the Wolfram Language, the command FindClique[g][[1]]
can be used to find a maximum clique, and FindClique[g,
Length /@ FindClique[g], All] to find all maximum
cliques. Similarly, FindClique[g,
Infinity] can be used to find a maximal clique,
and FindClique[g,
Infinity, All] to find all maximal
cliques. To find all cliques, enumerate all vertex subsets 
and select those for which CompleteGraphQ[g,
s] is true.
In general, FindClique[g, n] can be used to find a maximal clique
containing at most 
vertices, FindClique[g,
n, All] to find all such cliques, FindClique[g,
{n}] to find a maximal clique containing
exactly 
vertices,
and FindClique[g,
{n}, All] to find all such cliques.
The numbers of cliques, equal to the clique polynomial evaluated at 
, for various members of graph
families are summarized in the table below, where the trivial 0-clique represented
by the initial 1 in the clique polynomial is
included in each count. The index of each value list in the table starts at 1. An
X indicates that the family in that row is not defined for the corresponding parameter
value. For the antiprism graph, helm
graph, pan graph, prism
graph, sunlet graph, torus
grid graph, and web graph, the cited OEIS sequences
give the values for 
. The exceptional values
for 
are included separately in the table.
| graph family | OEIS | number of cliques |
| alternating group Cayley graph | A308599 | X, 2, 8, 45, 301, 2281, ... |
| Andrásfai graph | A115067 | 4, 11, 21, 34, 50, 69, 91, ... |
 antelope
graph | A308600 | 2, 5, 10, 17, 34, 61, 98, ... |
| antiprism graph | A017077 | X, X, 27, 33, 41, 49, 57, 65, ... |
| Apollonian network | A205248 | 16, 40, 112, 328, 976, 2920, ... |
| barbell graph | A000079 | X, X, 16, 32, 64, 128, 256, 512, ... |
 bishop
graph | A183156 | 2, 7, 22, 59, 142, 319, ... |
 black
bishop graph | A295909 | 2, 4, 14, 30, 82, 160, 386, ... |
book graph  | A016897 | 9, 14, 19, 24, 29, 34, 39, 44, ... |
| Bruhat graph | A139149 | 2, 4, 13, 61, 361, 2521, 20161, ... |
| centipede graph | A008586 | 4, 8, 12, 16, 20, 24, 28, 32, 36, ... |
cocktail party graph  | A000244 | 3, 9, 27, 81, 243, 729, 2187, ... |
complete graph  | A000079 | 2, 4, 8, 16, 32, 64, 128, 256, ... |
complete bipartite graph  | A000290 | 4, 9, 16, 25, 36, 49, 64, 81, 100, ... |
complete tripartite graph  | A000578 | 8, 27, 64, 125, 216, 343, 512, ... |
 -crossed
prism graph | A017281 | X, 21, 31, 41, 51, 61, 71, ... |
crown graph  | A002061 | 3, 7, 13, 21, 31, 43, 57, 73, 91, ... |
| cube-connected cycle graph | A295926 | X, X, 69, 161, 401, 961, 2241, 5121, ... |
cycle
graph  | A308602 | X, X, 8, 9, 11, 13, 15, 17, 19, ... |
| dipyramidal graph | A308603 | X, X, 24, 27, 33, 39, 45, 51, 57, 63, ... |
empty graph  | A000027 | 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ... |
| Fibonacci cube graph | A291916 | 4, 6, 11, 19, 34, 60, 106, 186, ... |
 fiveleaper graph | A308604 | 2, 5, 10, 17, 34, 73, 126, 193, 274, ... |
| folded cube graph | A295921 | X, 4, 16, 25, 57, 129, 289, 641, 1409, ... |
| gear graph | A016873 | X, X, 17, 22, 27, 32, 37, 42, 47, 52, ... |
grid graph  | A056105 | 2, 9, 22, 41, 66, 97, 134, 177, 226, 281, ... |
grid graph  | 2, 21, 82, 209, 426, 757, 1226, 1857, ... | |
| halved cube graph | A295922 | 2, 4, 16, 81, 393, 1777, ... |
| Hanoi graph | A295911 | 8, 25, 76, 229, 688, ... |
| helm graph | A016933 | X, X, 22, 26, 32, 38, 44, 50, 56, ... |
hypercube graph  | A132750 | 4, 9, 21, 49, 113, 257, 577, 1281, 2817, ... |
| Keller graph | A295902 | 5, 57, 14833, 2290312801, ... |
 king graph | A295906 | 2, 16, 50, 104, 178, 272, 386, ... |
 knight graph | A295905 | 2, 5, 18, 41, 74, 117, 170, 233, 306, 389, ... |
ladder graph  | A016897 | 4, 9, 14, 19, 24, 29, 34, 39, 44, 49, 54, ... |
ladder rung graph  | A016777 | 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, ... |
| Menger sponge graph | A292209 | 45, 1073, 22977, ... |
Möbius
ladder  | A016861 | X, X, 16, 21, 26, 31, 36, 41, 46, 51, ... |
| Mycielski graph | A199109 | 2, 4, 11, 32, 95, 284, 851, 2552, 7655, ... |
odd graph  | A295934 | 2, 8, 26, 106, 442, 1849, 7723, ... |
| pan graph | A005408 | X, X, 10, 11, 13, 15, 17, 19, 21, 23, ... |
path graph  | A005843 | 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, ... |
path complement graph  | A000045 | 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... |
| permutation star graph | A139149 | 2, 4, 13, 61, 361, 2521, ... |
| polygon diagonal intersection graph | A300524 | X, X, 8, 18, 41, 80, 169, 250, ... |
prism graph  | A016861 | X, X, 18, 21, 26, 31, 36, 41, 46, 51, ... |
 queen graph | A295903 | 2, 16, 94, 293, 742, 1642, 3458, 7087, ... |
rook graph  | A288958 | 2, 9, 34, 105, 286, 721, 1730, ... |
rook complement graph  | A002720 | 2, 7, 34, 209, 1546, 13327, 130922, ... |
| Sierpiński carpet graph | A295932 | 17, 153, 1289, 10521, ... |
| Sierpiński gasket graph | A295933 | 8, 20, 55, 160, 475, ... |
| Sierpiński tetrahedron graph | A292537 | 16, 59, 227, 899, 3587, 14339, ... |
star graph  | A005843 | 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, ... |
| sun graph | A295904 | X, X, 20, 32, 52, 88, 156, 288, 548, ... |
sunlet graph  | A016813 | X, X, 14, 17, 21, 25, 29, 33, 37, 41, 45, ... |
tetrahedral graph  | A289837 | X, X, X, X, X, 261, 757, 2003, 5035, ... |
torus grid graph  | A056107 | X, X, 34, 49, 76, 109, 148, 193, ... |
| transposition graph | A308606 | 2, 4, 16, 97, 721, 6121, ... |
| triangular graph | A290056 | X, 2, 8, 27, 76, 192, 456, 1045, ... |
| triangular grid graph | A242658 | 8, 20, 38, 62, 92, 128, 170, 218, ... |
triangular
snake graph  | A016789 | 2, X, 8, X, 14, X, 20, X, 26, X, 32, X, ... |
| web graph | A016993 | X, X, 24, 29, 36, 43, 50, 57, 64, 71, 78, ... |
wheel graph  | A308607 | X, X, X, 16, 18, 22, 26, 30, 34, 38, 42, 46, ... |
 white bishop graph | A295910 | 1, 4, 9, 30, 61, 160, 301, 718, ... |
Closed forms for some of these are summarized in the table below.
-
