# Minimum size of largest clique in graph

I'm having trouble with a problem from HackerRank, and I'm hoping someone here can enlighten me. The problem is stated like this:

What is the minimum size of the largest clique in any graph with N nodes and M edges?

The hints suggest using Turan's theorem, but it's not clear to me how to get from that to a solution.

How can I solve this problem, either with or without Turan's theorem?

The full questions is here.

• Did you look up Turán's theorem? That's a good thing to do if the theorem is given as a hint. Apr 5 '15 at 21:44
• Yes, of course I looked it up on Wikipedia. Apr 5 '15 at 22:38

Turán's theorem states that if a graph on $n$ vertices doesn't contain an $(r+1)$-clique then it has at most $\lfloor \frac{r-1}{r} \frac{n^2}{2} \rfloor$ edges. You take it from here.

• I'm not sure if the poster got the answer or not, but your answer just rephrases a hint that he already said he knew about. I fail to see how this is helpful. Jun 10 '15 at 17:41
• I think the following answer gives very good hint, I'm not sure how to offer it as it's not mine math.stackexchange.com/questions/1279241/… Jun 10 '15 at 17:54

Turan's theorem states the following:

If a graph with $n$ vertices does not contain a clique of size $r+1$, then the number of edges in that graph is at most $\frac{1}{2}(n^2 - (n\,\bmod\,r)\lceil n/r\rceil^2 - (r-(n\,\bmod\,r))\lfloor n/r\rfloor^2)$.

The former statement is equivalent to the following statement:

If a graph with $n$ vertices has more than $\frac{1}{2}(n^2 - (n\,\bmod\,r)\lceil n/r\rceil^2 - (r-(n\,\bmod\,r))\lfloor n/r\rfloor^2)$ edges, then it does contain a clique of size $r+1$.

The minimum size of the largest clique in any graph with $n \geq 2$ vertices and $m \geq 1$ edges can then be computed in a naive way as follows:

(1.) set $r=n-1$

(2.) compute $m^*(r) = \frac{1}{2}(n^2 - (n\,\bmod\,r)\lceil n/r\rceil^2 - (r-(n\,\bmod\,r))\lfloor n/r\rfloor^2)$

(3.) if $m > m^*(r)$ return $r+1$ else decrement $r$ by 1 and go to (2.)

The algorithm above runs in linear time. A more efficient solution runs in logarithmic time. The idea is to utilize binary search to find the value $r+1$ such that $m>m^*(r)$ and $m \leq m^*(r+1)$.

• I don't understand this for r>1 how can m> m*(r)? Jul 19 '17 at 20:27