# Size of maximum clique given a fixed amount of edges?

Given an undirected graph $G = (V,E)$, what is the clique number $\omega(G)$ given $|E|$, i.e., the size of the largest clique in a graph with $|E|$ edges.

I think this is doable after realizing that the number of edges in a clique is equal to the triangular number: $$|E(K_k)| = \frac{1}{2}k(k-1).$$

I am looking for a closed formula.

• Do you mean the maximal possible clique? Or finding the maximal clique size in a specific graph? The maximal possible size will clearly be $\min\{|V|,t\}$, where ${t\choose 2}=k$. Finding the maximal clique is NP-complete. Apr 16, 2013 at 19:22
• I'm looking for the maximal possible Clique. What does t refer to in this case? Apr 17, 2013 at 2:56
• $t$ is the solution to the equation $t(t-1)/2=k$. Intuitively - $t$ is the number of vertices you need for a clique with $k$ edges. Apr 17, 2013 at 5:11

The graph can have clique number 1 (if we allow the graph to be disconnected), or 2 (consider a long path). The graph can have a clique of size at most $$\frac{1}{2} (\sqrt{8m + 1} + 1),$$ where $m = |E|$, provided of course that $|V|$ is large enough.