Изменения

Пусть теперь ребро <tex> (u, v_1) \notin ET, v_i </tex> - первая вершина пути <tex> P </tex>, для которой ребро <tex> (u, v_i) \in T </tex>.

Если такая вершина существует, то в <tex> T </tex> существует ребро <tex> (v_{i - 1}, u) </tex> и путь <tex> (v_1 \rightarrow \ldots \rightarrow v_{i - 1} \rightarrow u \rightarrow v_i \rightarrow \ldots v_n) </tex> – гамильтонов.

Если такой вершины не существует, то путь <tex> (P \rightarrow u) </tex> - гамильтонов.

<u> Первый случай: </u>

: Пусть <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>.