графы - Гамильтонов цикл

Добавим к условию, что графы считаются простыми, и число вершин $%n$% не меньше трёх.

Разница между числом рёбер $%\frac{n(n-1)}2$% полного графа на $%n$% вершинах и числом рёбер рассматриваемого подграфа, которое не меньше $%f(n)=\frac{n^2-3n+6}2$%, составляет не больше $%n-3$%. Поэтому можно считать, что мы из полного графа удаляем $%n-3$% ребра, и надо доказать, что при этом получается гамильтонов граф. Отметим, что оценка является точной, так как удаление $%n-2$% рёбер, исходящих из одной вершины, привела бы уже к негамильтонову графу.

Проводим индукцию по $%n\ge3$%. При $%n=3$% всё очевидно. Пусть $%n > 3$%. Рассмотрим одно удаляемое ребро $%e$%, соединяющее вершины $%v$% и $%w$%. Остальные удаляемые рёбра, инцидентные $%v$%, не инцидентны $%w$%. Вместе их не больше $%n-4$%. Поэтому хотя бы для одной из этих вершин, которую можно считать равной $%v$%, число дополнительно удаляемых рёбер c началом $%v$%, не больше половины от этого числа, то есть $%\frac{n}2-2$%. Значит, остаётся не менее $%\frac{n}2$% рёбер с началом $%v$%, которые войдут в подграф.

Рассмотрим подграф $%G'$% на $%n-1$% вершине, не считая $%v$%. Легко видеть, что $%f(n)-f(n-1)=n-2$%, а удалили мы $%n-3$% ребра. Поэтому в $%G'$% останется более $%f(n-1)$% ребра, и к нему применимо индукционное предположение. Рассмотрим в $%G'$% гамильтонов цикл.

Вершина $%v$% соединена не менее чем с $%\frac{n}2$% вершинами этого цикла. Поэтому среди них найдутся две соседние в этом цикле. Тогда соединяющее их ребро цикла заменяем на два ребра, проходящие через $%v$%, и получаем гамильтонов цикл в $%G$%.