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

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

Предположим, что в новом графе образовался цикл четной длины. Тогда он должен проходить через То есть наш склеенный цикл соединен с некоторым путем по двум вершинам и лежащим в цикле. Но тогда по ребрам выбранного цикла между и существует путь четной длины. Заменим вершину на четный путь между и мы получим четный цикл в исходном графе, что противоречит условию. Значит, мы показали, что в новом графе также нет циклов четной длины. Если а ребер в выбранном цикле то количество ребер не превосходит Аналогично, если то получаем оценку

Осталось привести пример. Для нечетных выберем одну вершину, а остальные разобьем на пары соединенных, и от каждой пары проведем оба ребра в выбранную вершину. Если же четно, то делаем то же самое, но останется одна вершина без пары, ее просто соединим с выбранной.