Задача
COM-B2-M04-P007 Минимальная степень и цикл
#7
★★★☆☆ Уровень 3 из 5
В конечном графе степень каждой вершины не меньше \(2\). Докажите, что в графе есть цикл.
Рассмотрите самый длинный путь и его последний конец.
Выберем самый длинный путь \(v_1v_2\ldots v_k\). Все соседи вершины \(v_k\) лежат на этом пути, иначе путь можно было бы продолжить.
Так как степень \(v_k\) не меньше \(2\), кроме соседа \(v_{k-1}\) у неё есть ещё один сосед среди вершин пути. Пусть это \(v_i\), где \(i
Очень важная связка: самый длинный путь плюс условие на степень.