\proof Buď $W$ minimální $xz$-řez.
-\fig{4-ght-rez.eps}{\epsfxsize}
+\fig{4-ght-rez.epdf}{\epsfxsize}
\noindent Vrchol $y$ musí být v~jedné z~komponent, Pokud je v~komponentě s~$x$, pak $r(y,z) \le d(W)$,
protože $\d(W)$ je také $yz$-řez. Pokud v~té druhé, analogicky platí $r(x,y) \le d(W)$.
vrcholy z~$U$. Pak existuje množina vrcholů $W \subseteq U$ taková, že $\d(W)$ je minimální $uv$-řez.
\foot{To důležité a netriviální je, že celá $W$ leží v~$U$.}
-\fig{4-ght-htl.eps}{\epsfxsize}
+\fig{4-ght-htl.epdf}{\epsfxsize}
\proof Nechť je $\d(X)$ minimální $uv$-řez.
BÚNO můžeme předpokládat, že $s\in U$ a $t\not\in U$, $u\in X$ a $v\not\in X$ a $s\in X$.
\checkroom{40pt}
Nyní mohou nastat následující dva případy:\numlist\nalpha
-\vbox to 0pt{\vskip 10pt\rightline{\epsfysize=2.5cm\epsfbox{4-ght-htl-a.eps}}\vss}\vskip-\baselineskip
+\vbox to 0pt{\vskip 10pt\rightline{\epsfysize=2.5cm\epsfbox{4-ght-htl-a.epdf}}\vss}\vskip-\baselineskip
\:$t\not\in X$. Tehdy si všimneme, že platí:
\hangindent=-14em\hangafter=-100
$$\eqalignno{
Nyní stačí nerovnosti $(2)$ a $(1)$ odečíst, čímž získáme: $$d(U \cap X) \le d(X),$$
což spolu s~obrázkem dokazuje, že $\d(U \cap X)$ je také minimální $uv$-řez.
-\vbox to 0pt{\vskip 20pt\rightline{\epsfysize=2.5cm\epsfbox{4-ght-htl-b.eps}}\vss}\vskip-\baselineskip
+\vbox to 0pt{\vskip 20pt\rightline{\epsfysize=2.5cm\epsfbox{4-ght-htl-b.epdf}}\vss}\vskip-\baselineskip
\:$t\in X$. Postupovat budeme obdobně jako v~předchozím případě. Tentokrát se budou
hodit tyto nerovnosti:
\hangindent=-14em\hangafter=-100
do $v_1$ \<nejlevnější> hrana, která z~něj vedla do množiny $V\setminus W$, případně žádná, pokud
do této množiny žádná hrana nevedla.}
-\fig{4-ght-g1g2-before.eps}{0.45\hsize}
-\fig{4-ght-g1g2-after.eps}{0.9\hsize}
+\fig{4-ght-g1g2-before.epdf}{0.45\hsize}
+\fig{4-ght-g1g2-after.epdf}{0.9\hsize}
\finalfix{\bigskip}
Dále vytvoříme množiny vrcholů $R_1=R \cap \overline W$ a $R_2=R \cap W$. Dle indukčního
$s$ a $t$. Přitom ale separuje $r_1$ a $r_2$, takže musí separovat buď $s$ a $r_1$, nebo $t$ a $r_2$.
BÚNO nechť $X$ separuje $s$ a $r_1$.
-\fig{4-ght-rezx.eps}{12cm}
+\fig{4-ght-rezx.epdf}{12cm}
Podívejme se nyní na \PGHT{} $T_1$ (víme, že ten je korektní) a nalezněme v~něm nejlevnější hranu $e$ na cestě spojující $s$ a $r_1$.
Tato hrana definuje řez $\d(U)$, což je minimální $sr_1$-řez, podle HTL i v~celém~$G$. Protože $\d(X)$ je $sr_1$-řez,