Изменения

: Пусть <tex> v_1 </tex> - вершина из <tex> S_k </tex> такая, что ребро <tex> e = (v_1, v_0 ) \in ET </tex>. Пусть <tex> v_i </tex> – первая вершина при обходе <tex> S_k </tex> из <tex> v_1 </tex>, для которой ребро <tex> f = (v_0, v_i ) \in ET </tex>.

: Тогда ребро <tex> g = (v_{i - 1}, v_0) \in ET </tex>.

: Тогда <tex> S_{k + 1} = (v_1 \rightarrow v_2 \rightarrow \ldots \rightarrow v_{i - 1} \rightarrow v_0 \rightarrow v_i \rightarrow \ldots \rightarrow v_k \rightarrow v_1) </tex> – искомый цикл длины <tex> k + 1 </tex>.

[[Файл:cycle_k+1-2.png|150px|thumb|right|<tex> S_{k + 1} во втором случае. </tex>]]: Пусть::* <tex> V_1 = \{ u \in VT | u \notin S_k, e = (u, v_i) \in ET, \forall i = \overline{1, n} \} </tex>,:* <tex> V_2 = \{ u \in VT | u \notin S_k, f = (v_i, u) \in ET, \forall i = \overline{1, n} \} </tex>.: Тогда <tex> V_1 \cap V_2 = \emptyset </tex>.: Турнир сильно связен, следовательно::* <tex> V_1 \neq \emptyset </tex>, (иначе <tex> T </tex> не будет сильно связным, так как тогда нет простых путей с началом в <tex> V_2 </tex> и концом в <tex> {v_1, \ldots, v_k} </tex>):* <tex> V_2 \neq \emptyset </tex>, (иначе <tex> T </tex> не будет сильно связным, так как тогда нет простых путей с началом в <tex> {v_1, \ldots, v_k} </tex> и концом в <tex> V_1 </tex>):* <tex> \exists g = (w_2, w_1) \in ET </tex>, (иначе <tex>T</tex> не будет сильно связным, так как тогда нет простых путей с началом в <tex>V_2</tex> и концом в <tex>V_1</tex>)::** <tex> w_1 \in V_1 </tex>,:** <tex> w_2 \in V_2 </tex>.: Тогда <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>.