# Number of cliques in a graph

I think the number of cliques in a graph is generally exponential in the of vertices of that graph. Does anyone know any reference for that?

• I would recommend reading this: arxiv.org/abs/math/0602191
– ryan
Commented Jul 24, 2017 at 22:32
• What have you tried? Have you tried counting the number of cliques in the complete graph on $n$ vertices, as a function of $n$?
– D.W.
Commented Jul 24, 2017 at 22:48
• This is an extremely straightforward observation (consider @D.W.'s suggestion) and a citation isn't required. Sure, you could probably find somebody who's published this fact but giving them a citation would look silly and they certainly won't have been the first person to make the observation. Commented Jul 24, 2017 at 22:53
• @D.W. Thanks, for a complete graph of $n$ vertices, I think the number of cliques is $n \choose 1$ + $n \choose 2$ + $\ldots$ + $n \choose n$ = $2^n$. Am I right? Commented Jul 25, 2017 at 1:29

I am assuming you mean the number of maximal cliques, as the number of cliques of a complete graph is trivially $2^n$ (any subset of the vertices forms a clique).
For the number of maximal cliques, take the complement of a disjoint union of triangles. Since the number of maximal independent sets is exactly the same (in the complement), you can count the number of maximal independent set in a graph that is a disjoint union of triangles. This number is $3^{n/3}$ (Moon and Moser, 1965).