Условие:
Пусть
Докажите, что если в графе на n вершинах степень каждой вершины не меньше чем (n − k + 2), то граф обязательно содержит простой цикл, длина которого не превосходит k.
Решение:
то есть степень каждой вершины хотя бы 2, тогда если обозначить количество ребер в графе как m, а степень вершины v как dv, получаем
Отсюда получаем, что в нашем графе будет хотя бы один цикл. Действи...