Изменения

:Рассмотрим такой поток <tex>f'</tex>, что <tex>f'(uv) \neq f(uv)</tex>. Поскольку <tex>p_{\varphi}(uv) \geqslant 2V\varepsilon > \varepsilon</tex>, поток по ребру <tex>uv</tex> должен быть как можно меньше, то есть <tex>f(uv) = -c(uv)</tex>, и тогда раз <tex>f'(uv) \neq f(uv)</tex>, то <tex>f'(uv) > f(uv)</tex>.

:Обозначим за <tex>G_{>}</tex> подграф <tex>G</tex> такой, что <tex>G_{>}=(V, \{uv \in E \;|\; f'(uv) > f(uv) \})</tex>. Рассмотрим какое-то некоторое ребро <tex>uv</tex> в <tex>G_{>}</tex>. Поскольку <tex>f</tex> и <tex>f'</tex> являются циркуляциями, в <tex>G_{>}</tex> должен содержаться простой цикл <tex>C</tex>, проходящий через <tex>uv</tex>. Поскольку все ребра в <tex>C</tex> {{---}} остаточные, стоимость <tex>C</tex> {{---}} как минимум не меньше <tex>p_{\varphi}(uv) - (\texttt{len}(C)-1)\varepsilon \geqslant 2V\varepsilon - (V-1)\varepsilon > V\varepsilon</tex>.:Теперь рассмотрим цикл <tex>\overline{C}</tex>, который получен из <tex>C</tex> разворотом всех его ребер. Заметим, что <tex>\overline{C}</tex> является циклом в <tex>G_{<}=(V,\{uv \in E \;|\; f'(uv) < f(uv)\})</tex> и, соответственно, циклом в <tex>G_{f}</tex>. По свойству антисимметричности, стоимость <tex>\overline{C}</tex> меньше, чем <tex>-nV\varepsilon</tex> и, таким образонобразом, средний вес <tex>\mu(\overline{C}) </tex> меньше чем <tex>-\varepsilon</tex>. Откуда, по [[#lemma3|лемме]] имеем, что <tex>f'</tex> не <tex>\varepsilon</tex>-оптимален.