Изменения

Для доказательства мы будем ползьоваться пользоваться развитой раннее [[Определение сети, потока|теорией потоков]]. Кроме базовых определений нам потребуется понятие [[Дополняющая сеть, дополняющий путь| остаточной сети]] (иначе - дополнительной сети), а также [[Теорема_Форда-Фалкерсона|теорема Форда-Фалкерсона]].  //что-то про разрез .. [[Разрез, лемма о потоке через разрез]] Кроме того потребуется лемма о целочисленности потока, которую сейчас и докажем:

Теперь сама теорема будет тривиальным следствием. В начале сформулируем и докажем реберную версию для случая ориентированного графа.

Назначим каждому ребру пропускную способность 1.  <=Тогда существует максимальный поток , целочисленный на каждом ребре(по лемме). Рассмотрим минимальныйПо теореме Форда-Фалкерсона для такого потока существует разрез с пропускной способностью равной потоку (и этот разрез минимален среди всех возможных разрезов). По условию "после удаления <tex>\forall L-1</tex> (и в частности тех, что находятся в нашем разрезе) ребер все еще<tex>\exists</tex> путь из <tex>u</tex> в <tex>v</tex>", значит пропускная способность разреза <tex>\geqslant L = |f|</tex>. А т.к. поток целочисленный , то это и означает, что <tex>\exists L</tex> реберно непересекающихся путей (чуть позже дадим аккуратное объяснение этому). =><tex>\exists L</tex> реберно непересекающихся путей, а значит удалив любых <tex>L-1</tex> ребер хотя бы один путь останется останется не тронутым (принцип Дирихле). Это и означает <tex>\exists</tex> путь из <tex>u</tex> в <tex>v</tex>.