Изменения

Заметим, что при <tex>k = n - 1</tex> такая вершина необходимо существует, так как иначе вершина, не входящая в цикл, будет являться либо стоком, либо истоком.

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

* <tex> V_1 \neq \emptyset </tex>, (иначе <tex> T </tex> не будет сильно связным, так как тогда нет простых путей с началом в <tex> V_2 </tex> и концом в <tex> {v_1, \ldots, v_k} S_k </tex>)* <tex> V_2 \neq \emptyset </tex>, (иначе <tex> T </tex> не будет сильно связным, так как тогда нет простых путей с началом в <tex> {v_1, \ldots, v_k} S_k </tex> и концом в <tex> V_1 </tex>)

{{ЛеммаТеорема