Upper bound on number of edges in graph with no clique of size k as subgraph

Question

Let $G = (V, E)$ be an undirected graph such that $|V| = n$ and $G$ doesn't have a clique of size k as a subgraph. I need an upper bound on $|E|$. Any ideas? I'm hoping for $O(nk)$ but can't prove it.

Thanks!

Answer 1

Since Turán's theorem is the right hint and it is already given in the comments, I am going to give an easy counterexample, which actually is a direct consequence of Turán's theorem, to your "hope" that the upper bound is $O(nk)$. First, let us recapitulate the statement as provided here.

Theorem 1 (Turán): Let $G$ be a graph on $n$ vertices that does not contain a $K_{r+1}$ as a subgraph. Then $|E(G)| \leq \frac{r-1}{r}\cdot \frac{n^2}{2}=(1-\frac{1}{r})\cdot \frac{n^2}{2}$

For the special case $r=2$, a triangle free graph, the maximum number of edges edges for a $n$-vertex graph is $\lfloor \frac{n^2}{4} \rfloor $. To formalize:

Corollary 1: Let $G_n$ be a bipartite graph on $n$ vertices, then $|E(G_n)| \leq \lfloor \frac{n^2}{4} \rfloor$.

It is easy to see that $\lfloor \frac{n^2}{4} \rfloor$ is not bounded from above by $nk$ for fixed $k \in \mathbb{N}$ (in this case $k=3$) for all $n$. To be precise, it fails for all $n>4$.