Изменения
Нет описания правки
{{Утверждение
|statement=
Если сильно связанный турнир <tex> T </tex> из <tex> n \geq 3 </tex> вершин содержит цикл <tex> S_k </tex> длины <tex> k , (k < n)</tex>, то он содержит и цикл длины <tex> k + 1 </tex>.
|proof=
Пусть <tex> S_k = (v_1 \rightarrow v_2 \rightarrow \ldots \rightarrow v_k \rightarrow v_1) </tex>.
# существует такая вершина <tex> v_0 </tex>,
# не существует такой вершины <tex> v_0 </tex>.
Заметим, что при <tex>k = n - 1</tex> такая вершина необходимо существует, так как иначе вершина, не входящая в цикл, будет являться либо стоком, либо истоком.
<u> Первый случай: </u>
: Тогда <tex> S_{k + 1} = (v_1 \rightarrow w_2 \rightarrow w_1 \rightarrow v_3 \rightarrow \ldots \rightarrow v_k \rightarrow v_1) </tex> – искомый цикл длины <tex> k + 1 </tex>.
В любом случае утверждение верно , q.e.d.
}}
Таким образом, в любой сильно связанный турнир <tex> T </tex> из с <tex> n \geq 3 </tex> вершин вершинами содержит цикл длины <tex> n </tex>, то есть гамильтонов цикл, q.e.d.
}}
