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

Для начала договоримся, что будем доказывать более сильную задачу, а именно, что длина самого длинного просто пути Будем доказывать по индукции по количеству вершин. База для одной вершины очевидна. Теперь переход. Давайте посмотрим на самый длинный путь. Рассмотрим один из его концов. Обозначим его за Заметим, что все ребра из могу вести только в этот путь, иначе будет противоречие с максимальностью этого пути. Следовательно, степень вершины меньше, чем Тогда давайте удалим вершину и по предположению раскрасим граф, который остался, а потом покрасим в свободный от цвета соседей вершину и получим правильную раскраску всего графа.