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.
-
