-Ji¾ víme, ¾e~$\min_{(A,B)} c(A,B) \geq \max_f \vert f \vert$. Staèí tedy dokázat, ¾e~v¾dy existuje tok $f$ a~øez ($A,B$) takové, ¾e~$c(A,B) = \vert f \vert$. Pro~racionální kapacity nám Fordùv-Fulkersonùv algoritmus takový tok (maximální) a~øez (minimální) vydá. Jak je to ale s~reálnými kapacitami? Vyu¾ijeme tvrzení, ¾e~maximální tok existuje v¾dy. Pak mù¾eme spustit Fordùv-Fulkersonùv algoritmus rovnou na~tento maximální tok. Algoritmus se~nutnì ihned zastaví, nebo» neexistuje cesta, která by mìla alespoò jednu hranu s~kladnou rezervu. A~my víme, ¾e~pokud se~algoritmus zastaví, tak vydá minimální øez. Proto i~pro sí» s~reálnými kapacitami platí, ¾e~existuje maximální tok $f$ a~minimální øez $(A,B)$ a $c(A,B) = \vert f \vert$.
+Ji¾ víme, ¾e~$\min_{(A,B)} c(A,B) \geq \max_f \vert f \vert$. Staèí tedy dokázat, ¾e~v¾dy existují tok $f$ a~øez ($A,B$) takové, ¾e~$c(A,B) = \vert f \vert$. Pro~racionální kapacity nám Fordùv-Fulkersonùv algoritmus takový tok (maximální) a~øez (minimální) vydá. Jak je to ale s~reálnými kapacitami? Vyu¾ijeme tvrzení, ¾e~maximální tok existuje v¾dy. Pak mù¾eme spustit Fordùv-Fulkersonùv algoritmus rovnou na~tento maximální tok (místo nulového). Algoritmus se~nutnì ihned zastaví, nebo» neexistuje cesta, která by mìla alespoò jednu hranu s~kladnou rezervou. A~my víme, ¾e~pokud se~algoritmus zastaví, tak vydá minimální øez. Proto i~pro sí» s~reálnými kapacitami platí, ¾e~existuje maximální tok $f$ a~minimální øez $(A,B)$ a $c(A,B) = \vert f \vert$.