2
|statement=
Количество дополняющих путей с масштабом <tex> 2^k </tex> не превосходит <tex> 2E </tex>.|proof= На предыдущей итерации по предыдущей лемме. Следовательно, Суммарное количество дополняющих увеличивающих путей не превосходит <tex> 2E </tex>.{{---}} {{Лемма|about=2|statement=Общее количество увеличивающих путей не превышает <tex> O(E \log U) </tex>.
|proof=
На некоторой итерации алгоритма каждый дополняющий путь имеет пропускную способность не меньше <tex> 2^k </tex>.
Дополняющий поток на предыдущей итерации ограничен значением <tex> 2^{k + 1} E </tex>. Следовательно, на каждой итерации количество дополняющих путей не превосходит <tex> 2E </tex>.
Следует из предыдущей леммы и фактаКоличество итераций алгоритма {{---}} <tex> O(\log U) </tex>, значит, что суммарное количество итераций увеличивающих путей {{---}} <tex> O(E \log U) </tex>.
}}
