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

(a) Индукция по числу вершин

База: Для путь существует тривиально.

Переход: Пусть для турнира с вершинами существует гамильтонов путь Добавим вершину Если новый путь: Если новый путь: Иначе найдётся первый такой, что Вставим между и Получаем гамильтонов путь для

(b) Пусть — произвольная вершина. Рассмотрим её соседей:

• — вершины, в которые ведут рёбра из
• — вершины, из которых ведут рёбра в

Так как граф сильно связен, и Если существует ребро для то цикл: Иначе все рёбра между и направлены из в Но тогда граф не сильно связен, так как нельзя добраться из в Противоречие.

(c) Рассмотрим максимальный цикл Если он содержит все вершины, то он гамильтонов, пусть это не так. Рассмотрим вершину не лежащую в этом цикле. Если найдется пара стрелок вида то вершину можно добавить в цикл, противоречие, цикл — максимальный. Значит все стрелки направленны, либо от вершины к либо наоборот. Не умаляя общности стрелки идут в Но граф сильно связен, значит от есть путь до обозначим его за и пусть он кончается в вершине тогда цикл снова можно удлинить заменив стрелку на путь из стрелок противоречие.

(d) Пусть — сильно связный полный ориентированный граф с гамильтоновым циклом Если есть хотя бы одна стрелка вида то можно удалить вершину Пусть все стрелки такого вида ориентированны Они тогда образуют цикл, проход по которому, эквивалентен проходу по стрелке

Если цикл нечетный, тогда подойдет путь вида (нумерация по модулю ). Например для пяти: вместо прохода по стрелке пройдем путем:

Если цикл четный, то путь выглядит просто

В обоих случаях можно удалить вершину без потери связности.