Теорема Турана

Теорема Турана ( $P.Tur\acute{a}n, 1941$ ) — Пусть $\,n$ и $\,k$ — два целых числа ( $n \geq k \geq 1$ ) и пусть $\,G_{n,k}$ — граф, состоящий из $\,k$ непересекающихся клик из $\lceil n/k \rceil$ и $\lfloor n/k \rfloor$ вершин. Если $\,G$ — граф с $\,n$ вершинами и неплотностью $\,\alpha(G) = k$ , то число ребер $|E(G)| \geq |E(G_{n,k})|$ и равенство имеет место тогда и только тогда, когда $\,G$ изоморфен $\,G_{n,k}$ .