Изменения

Cильно связанный турнир <tex> T </tex> из <tex> n \geq 3 </tex> вершин содержит [[Основные_определения_теории_графов#.D0.9E.D1.80.D0.B8.D0.B5.D0.BD.D1.82.D0.B8.D1.80.D0.BE.D0.B2.D0.B0.D0.BD.D0.BD.D1.8B.D0.B5_.D0.B3.D1.80.D0.B0.D1.84.D1.8B|цикл]] длины <tex> 3 </tex>.

|proof=

Пусть <tex> u </tex> - произвольная вершина турнира <tex> T </tex>. Множество вершин <tex> VT - u </tex> распадается на <tex> 2 </tex> непересекающихся множества:

* <tex> V_1 = \{ v_1 \in VT | (v_1, u) \in ET \} </tex>,

* <tex> V_2 = \{ v_2 \in VT | (u, v_2) \in ET \} </tex>.

<tex> T </tex> сильно связен, следовательно:

#* <tex> w_1 \in V_1 </tex>,

#* <tex> w_2 \in V_2 </tex>.

Цикл <tex> S_3: (u \rightarrow w_2 \rightarrow w_1 \rightarrow u) </tex> - искомый цикл длины <tex> 3 </tex>, q.e.d.

}}