Изменения

# Индукционный переход <br> Предположим, что теорема верна для всех турниров с n вершинами. Рассмотрим турнир T с n + 1 вершинами. Пусть <math>v_0</math> – произвольная вершина турнира T. Тогда турнир T – <math>v_0</math> имеет n вершин, значит, в нем есть гамильтонов путь P: <math>v_1v_2...v_n</math> . Одно из ребер ( <math>v_0</math>, <math>v_1</math> ) или ( <math>v_1</math>, <math>v_0</math> ) обязательно принадлежит содержится в T. Рассмотрим 3 случая: ## Ребро ( <math>( v_0</math>, <math>v_1 ) \in T </math> ) принадлежит Т . Тогда путь <math>v_0v_1v_2...v_n</math> является гамильтоновым. ## Обозначим через <math>v_i</math> первую вершину пути P, для которой ребро ( <math>( v_0</math>, <math>v_i ) \in T </math> ) принадлежит T ,если такая вершина есть. Тогда в T существует ребро ( <math>v</math>_{<math>i-1</math>}, <math>v_0</math> ) <br> и путь <math>v_1...v</math>_{<math>i-1</math>}<math>v_0v_i...v_n</math>– гамильтонов.

# База индукции: <br> Покажем, что в любом сильно связанном турнире T с n вершинами (n >= 3) есть орцикл длины 3. Выберем произвольную вершину <math>v_0</math> и обозначим через <math>W</math> множество всех вершин <math>w</math>, таких, что ребро ( <math>( v_0</math>, <math>w ) \in T </math> ) в T, а через <math>Z</math> – множество всех вершин <math>z</math>, таких, что ребро ( <math>( z</math>, <math>v_0 ) \in T </math> ) в T. Так как T сильно связан, то оба множества <math>W</math> и <math>Z</math> не пусты и найдется ребро ( <math>( w'</math>, <math>z') \in T </math> ) , где <math>w'</math> принадлежит <math>\in W</math>, <math>z'</math> принадлежит <math>\in Z</math>. Тогда искомым циклом длины 3 будет <math>v_0</math>,<math>w'</math>,<math>z'</math>,<math>v_0</math>.

## Существует такая вершина <math>v_0\notin S </math> , не принадлежащая орциклу S и такая, что найдутся вершины <math>u</math> и <math>, w\in S</math>, принадлежащие орциклу S, такие, что ребра ( <math>( v_0</math>, <math>u</math> ) и , ( <math>w</math>, <math>v_0) \in T </math> ) содержатся в T. Обозначим за <math>v_1</math> вершину из S, такую, что ребро ( <math>( v_1</math>, <math>v_0 ) \in T </math> ) содержится в T. Пусть <math>v_i</math> – первая вершина при обходе контура S из <math>v_1</math>, для которой ребро <br> ( <math>( v_0</math>, <math>v_i ) \in T </math> ) принадлежит Т. Тогда ребро ( <math>v</math>_{<math>i-1</math>}, <math>v_0</math> ) также содержится в T. Поэтому <math>v_1v_2...v</math>_{<math>i-1</math>}<math>v_0v_i...v_kv_1</math> – искомый орцикл длины k+1.## Пусть такой вершины <math>v_0</math> нет. Тогда разобьем вершины, не принадлежащие S, на два непересекающихся подмножества <math>W</math> и <math>Z</math>, где <math>W</math> - множество таких вершин <math>w</math> , что ребро ( <math>v_i</math>, <math>w</math> ) для любого <math>i</math> содержится в T, а <math>Z</math> – множество таких вершин <math>z</math>, что ребро ( <math>z</math>, <math>v_i</math> ) для любого <math>i</math> содержится в T. Так как T сильно связан, то оба множества <math>W</math> и <math>Z</math> не пусты и найдется ребро ( <math>( w'</math>, <math>z') \in T </math> ) , где <math>w'</math> принадлежит <math>\in W</math>, <math>z'</math> принадлежит <math>\in Z</math>. Тогда <math>v_1wv_1 w'z'v_3...v_kv_1v_k v_1</math> – требуемый орцикл.