Задача
COM-B2-M04-P015 Длинный цикл из минимальной степени
В конечном графе степень каждой вершины не меньше \(k\), где \(k\ge 2\). Докажите, что в графе есть цикл, содержащий не менее \(k+1\) вершины.
Возьмите самый длинный путь и посмотрите на всех соседей его последней вершины.
Выберем самый длинный путь \(v_1v_2\ldots v_m\). Все соседи вершины \(v_m\) лежат на этом пути, иначе путь можно было бы продолжить.
У вершины \(v_m\) не меньше \(k\) соседей среди вершин \(v_1,\ldots,v_{m-1}\). Пусть \(v_i\) — самый ранний из этих соседей на пути. Тогда среди вершин \(v_i,v_{i+1},\ldots,v_{m-1}\) находится не меньше \(k\) соседей вершины \(v_m\), поэтому \(m-i\ge k\).
Рёбра пути от \(v_i\) до \(v_m\) вместе с ребром \(v_m v_i\) образуют цикл \(v_i v_{i+1}\ldots v_m v_i\). В нём \(m-i+1\ge k+1\) вершин.
Усиление базовой задачи о цикле: нужно не только найти цикл, но и оценить его длину.