Изменения

Существуют положительные вещественные числа <tex>c_{1}</tex> и <tex>c_{2}</tex>, такие что для любых натуральных <tex>V</tex> и <tex>E</tex>, удовлетворяющих неравенствам <tex>c_{1}V \le E \le c_{2}V^2</tex>, существует [[Определение сети, потока|сеть]] <tex>G</tex> с <tex>V</tex> вершинами и <tex>E</tex> ребрами, такая что для любого максимального потока <tex>f</tex> в <tex>G</tex>, любая его остаточная декомпозиция должна содержать <tex>\Omega (E)</tex> слагаемых (т.е. путей или циклов), причем каждый из путей (циклов) в декомпозиции должен иметь длину <tex>\Omega (V)</tex>.

|proof=

<div>Используются <tex>c_{1} = \frac{11}{10}</tex> и <tex>c_{2} = \frac{1}{9}</tex> ( <tex>\frac{11}{10} V \le E \le \frac{V^2}{9}</tex>). Чтобы получить искомую сеть, строится сеть, изображенная на рисунке, после чего добавляется нужное количество ребер из <tex>A</tex> в <tex>B</tex> (а именно, <tex>E-V+1</tex> ребро). Пропускные способности ребер из <tex>A</tex> в <tex>B</tex> равны <tex>1</tex>, остальных — <tex>+\infty</tex> (или просто достаточно большое число, например, <tex>V^2</tex>).</div>

Теперь докажем саму теорему: