Лемма. В сильно связном турнире $T$ существует гамильтонов цикл.

Доказательство. В сильно связном турнире есть циклы. Рассмотрим в нашем турнире $T$ максимальный простой цикл $C = a1a2...ak.$ Предположим, что в него вошли не все вершины графа, пусть вершина $b$ не вошла в этот цикл. Пусть не все стрелки между $b$ и циклом $C$ ориентированы одинаково. Тогда существуют последовательные вершины цикла $ai$ и $ai+1$ такие, что $aib,bai+1 ∈A(T).$ В этом случае несложно удлинить максимальный цикл $C,$ вставив вершину $b$ между $ai$ и $ai+1,$ противоречие.

Пусть из всех вершин цикла $C$ стрелки входят в $b.$ Ввиду сильной связности турнира $T$ существует путь $S$ от $b$ до цикла $C.$ Пусть $S$ впервые пересекает цикл $C$ в вершине $ai+1.$ Тогда, опять же, несложно удлинить наш максимальный цикл, заменив стрелку $aiai+1$ на путь $aibSai+1.$ Противоречие. Случай, когда из $b$ выходят ребра ко всем вершинам цикла $C,$ аналогичен. _________________________________________________________________________________________

Вернемся к доказательству основной задачи. По лемме в $G$ есть гамильтонов цикл $Z =a1a2...an$ . Нумерация вершин — циклическая, то есть $ai+n = ai.$ Пусть длина диагонали $aiaj$ цикла $Z$ — это остаток от деления на $n$ числа $j− i.$

Если количество вершин в $G$ равно $3$ или $4,$ то $G$ почти транзитивен.

Далее $n≥ 5.$ Рассмотрим два случая. Будем говорить, что $xy ∈ G.$ если в $G$ ребро между $x$ и $y$ направлено к $y.$

1. Для каждого $i$ выполняется $aiai+2 ∈ G.$

Тогда пусть $A$ состоит из всех вершин с нечётными номерами, $B$ — из $a1$ и всех вершин с чётными номерами. Нетрудно видеть, что $A ∩B = {a1},$ а индуцированные турниры $G(A )$ и $G (B )$ — сильно связные.

2. Существует диагональ $ai+2ai ∈ G.$

Не умаляя общности будем считать, что $a1an−1 ∈G.$ Докажем, что при $1≤ i<j ≤n − 1$ диагональ $aiaj ∈ G.$ Пусть это не так, тогда выберем диагональ $axay ∈ G,$ где $x,y ∈{1,...,n − 1},x> y$ и $x− y$ — максимально. Понятно, что выполняется хотя бы одно из условий $x⁄= n− 1$ и $y ⁄= 1.$ Пусть $x⁄= n− 1$ (второй случай аналогичен). Тогда $ayax+1 ∈ G,$ следовательно, для множеств $A = {ay,ay+1,...,ax}$ и $B = {ax+1,...,an,a1,...,ay}$ индуцированные турниры $G(A)$ и $G (B )$ сильно связны, $A∩ B = {ay}.$ В этом случае утверждение доказано.

Итак, при $i,j ∈{1,...,n− 1}$ и $i< j$ мы имеем $aiaj ∈G.$ Осталось разобраться, как направлены стрелки, инцидентные $an.$ Если существует такое $i{1,...,n − 2},$ что $aian,anai+1 ∈G,$ то множества

A= {an,a1,...,ai} и B = {ai+1,ai+2,...,an}

таковы, что турниры $G(A)$ и $G(B)$ сильно связны и $A∩ B ={an}.$ В этом случае утверждение доказано.

Остаётся случай, когда для некоторого $k ∈{1,...,n− 2}$ в нашем графе стрелки ориентированы таким образом:

ana1,...,anak ∈G, ak+1an,...,an− 1an ∈G

При $k= n− 2$ турнир $T$ почти транзитивен (с порядком $an,a1,...,an−1$ ). При $k =1$ турнир $T$ почти транзитивен (с порядком $a1,...,an−1,an$ ). Если же $k∈{1,...,n− 3},$ то $ak−1ak+2 ∈G.$ Следовательно, множества $A = {ak,ak+1,an}$ и $B =G ∖{ak,ak+1}$ таковы, что $G(A )$ и $G (B )$ сильно связны и $A∩ B = {an}.$

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