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

то есть степень каждой вершины хотя бы 2, тогда если обозначить количество ребер в графе как m, а степень вершины v как d_v, получаем

Отсюда получаем, что в нашем графе будет хотя бы один цикл. Действи...