Индукция в графах и теорема Турана

Докажем индукцией по числу вершин.

База индукции для четырёх вершин верна, поскольку из условия сразу следует, что вершины разбиваются на группы, состоящие из трёх и одной оставшейся вершин соответственно.

Пусть теперь для вершин уже получено разбиение на две доли по предположению индукции и теперь мы думаем, куда добавить вершину чтобы получить разбиение на две доли для вершин.

Если смежна со всеми вершинами из группы с попарно смежными, добавим её туда. В противном случае ( соединена с какой-то вершиной из второй группы) докажем, что мы сможем её добавить во вторую группу.

Пусть вершина не соединена с вершиной из первой группы, а вершина — с вершиной (если соединена со всеми в первой группе, то перекинем её туда). Если то четвёрка вершин и не удовлетворяет условию. Если возьмём произвольную вершину из первой группы и заметим, что четвёрка будет удовлетворять условию только если с ней будет соединена вершина Получается, что соединена со всеми вершинами из первой группы, кроме Поместим в первую группу, а — во вторую и продолжим алгоритм.

Число вершин, с которыми смежна, во второй группе уменьшилось, следовательно, такой процесс конечен и мы определим во вторую группу.