# Maximum number of cliques of size $\ge 2$ of a graph with exactly $m$ edges

Let $$G=(V,E)$$ be an undirected graph with $$|E|=m$$ edges.

Given that any clique of size $$\ge 2$$ can be identified with its corresponding edges, and at most every subset $$S\subseteq E$$ creates a clique, $$G$$ can have at most $$|P(E)|= 2^m$$ cliques of size $$\ge 2$$.

However, based on the intuition that it's better to arrange the edges into bigger cliques, I'd assume arranging the $$m$$ edges into one big clique of size $$c$$ is optimal (whenever it's possible). If $$c$$ is the size of that clique, we have $$m=\binom{c}2 \rightarrow c\le 4\sqrt m$$, and I'd therefore assume that one can get an upper bound of the form $$2^{4\sqrt m}$$.

How would one show this upper bound?

Noting in above simple proof that only subsets $$S$$ with size $$\left|S\right|=\binom{i}2$$ for some $$i\in \mathbb N$$ can ever be edge sets of a clique doesn't seem to help.

• I would try to show that a maximum number of cliques can be achieved when the $m$ edges are incident on as few vertices as possible (which is a clique when $m$ is a triangular number). I would try to do this by showing that, given an arbitrary $m$-edge graph, if there is a vertex $v$ all of whose incident edges can be moved to other pairs of vertices that are already both of nonzero degree (note there is a wrinkle for neighbours of $v$), then doing so (which reduces the total number of vertices incident on any edge, bringing us closer to a clique) never reduces the number of cliques. Commented Aug 19, 2021 at 15:46
• You can take a look at similar proofs of Turán's theorem for inspiration. Commented Aug 20, 2021 at 3:39

In this paper with DOI 10.1007/s00373-007-0738-8 we have the following theorem:

Let $$n$$ and $$m$$ be non-negative integers such that $$m ≤ \binom n2$$. Let $$d$$ and $$l$$ be the unique integers such that $$m =\binom d2+l$$, where $$d ≥ 1$$ and $$0 ≤ l ≤ d − 1$$.
Then the maximum number of cliques in an $$(n, m)$$-graph equals $$2^d + 2^l + n − d − 1$$.

Here, an $$(n,m)$$-graph is a graph with $$n$$ nodes and $$m$$ edges.

This graph has $$n$$ 1-cliques and $$1$$ 0-clique.

Therefore its number of cliques of size $$\ge 2$$ is $$2^d + 2^l − d − 2 \le 2^{d+1} − d − 2\le 2^{d+1}$$ and $$d$$ is the biggest integer with $$m\ge \binom{d}2$$.

So we further have $$d\le \frac{\sqrt{8·m+1}+1}2$$

Assuming $$m\ge 1$$, we have $$\frac{\sqrt{8·m+1}+1}2\le \frac{\sqrt{9m}+1}2 = \frac{3\sqrt m+1}2\le 2\sqrt m$$

And with that, we get that the number of cliques of size $$\ge 2$$ is upper bounded by $$2^{2\sqrt m+1}=2\cdot 4^\sqrt m$$