272
правки
Изменения
Нет описания правки
Пусть предположение верно для всех турниров с количеством вершин не более <tex> n </tex>. Рассмотрим турнир <tex> T </tex> с <tex> n + 1 </tex> вершинами.
Пусть <tex> u </tex> – произвольная вершина турнира <tex> T </tex>. Тогда турнир <tex> T - u </tex> имеет <tex> n </tex> вершин, значит, в нем есть гамильтонов путь <tex> P: (v_1 \rightarrow v_2 \rightarrow \ldots \rightarrow v_n) </tex>. [[Файл: Redei_kamion_3.png|250px|thumb|center]]
Одно из ребер <tex> (u, v_1) </tex> или <tex> (v_1, u) </tex> обязательно содержится в <tex> T </tex>.
Значит, в любом случае в турнире существует гамильтонов путь, q.e.d.
}}
#* <tex> w_1 \in V_1 </tex>,
#* <tex> w_2 \in V_2 </tex>.
[[Файл: Redei_kamion_2.png|250px|thumb|center|<font color=#ED1C24>Красным</font> цветом выделен цикл длины <tex> 3</tex>]]
Цикл <tex> S_3: (u \rightarrow w_2 \rightarrow w_1 \rightarrow u) </tex> - искомый цикл длины <tex> 3 </tex>, q.e.d.
