Простой путь, Гамильтонов путь, Гамильтонов цикл

Рассмотрим ориентированный граф, в котором вершины — города, ребра — дороги. Из условия, что на любых 16 вершинах есть циклический маршрут, мы понимаем, что из каждой вершины выходит не менее 13 дорог (иначе можно взять вершину и 15 городов, в которые из неё не ведут дороги, и там не найдется цикла), аналогично в каждую входит не менее 13 дорог. Итого, для каждой вершины есть максимум одна, с которой она не соединена. Рассмотрим произвольные 17 вершин. Они не могут разбиться на пары несмежных, поэтому одна из них, назовем её соединена с каждой из 16 оставшихся. Построим на них цикл Пусть ребро направлено от к (иначе в дальнейшем будем двигаться по циклу в другую сторону). Если от идет ребро к то можно проход заменить на проход и получить цикл длины 15. Значит, от идет ребро к Таким образом можно сдвигаться на 3 вершины по циклу. Так как НОД мы обойдем весь цикл и получим, что от всех идет ребро к Но тогда на вершинах …, нельзя построить цикл.