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

Докажем индукцией по количеству вершин. Если в графе одна вершина, то утверждение задачи очевидно.

Пусть в графе вершин. В графе есть такая вершина при выкидывании которой граф не теряет связность. Выкинем её. В оставшемся графе по предположению индукции проведём нужную раскраску. Вернём вершину

Какая проблема могла возникнуть при возврате Чтобы не была одного цвета с одним из соседей, просто покрасим её в один из цветов, в который не покрашены соседи (такие цвета есть, потому что соседей не больше а цветов ).

Могло так оказаться, что какие-то соседи одного цвета, тогда при возврате одноцветные вершины имеют общих соседей. Рассмотрим вершины смежные с ней. Также рассмотрим вершины, с которыми соединены все Всего рассмотренных вершин вместе с не более Следовательно есть хотя бы цветов, в которые не покрашены ни одна из рассмотренных вершин. Покрасим вершины в эти цвета (каждую в свой цвет). Тогда все будут разных цветов и одноцветные вершины не будут иметь соседей. Что и требовалось.