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

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

Литература

• Berge C. Graphs (second revised edition). — Amsterdam; New York; Oxford: North-Holland, 1985.

• [math]\displaystyle{ Lov\acute{a}sz\,\, L.\,\, Combinatorial\,\, problems\,\, and\,\, exercises.\,\, -\,\, Budapest:\,\, Acad\acute{e}miqi\,\, Kiado,\,\, 1979. }[/math]