Turán's Theorem

Let $G(V,E)$ be a Graph with Vertices $V$ and Edges $E$ on $n$ Vertices without a $k$-Clique. Then

$$t(n,k)\leq {(k-2)n^2\over 2(k-1)},$$

where $t(n,k)=\vert E\vert$ is the Edge Number. More precisely, the K-Graph $K_{n_1, \ldots, n_{k-1}}$ with $\vert n_i-n_j\vert\leq 1$ for $i\not=j$ is the unique Graph without a $k$-Clique with the maximal number of Edges $t(n,k)$.

See also Clique, K-Graph, Turán Graph

References

Aigner, M. ``Turán's Graph Theorem.'' Amer. Math. Monthly 102, 808-816, 1995.