How to prove that the dual linear program of the max-flow linear program indeed is a min-cut linear program?
We can write the constraints on the $d_{uv}$ as follows:
$$ d_{uv} \geq z_u - z_v, z_v - z_u $$
$$ d_{sv} \geq 1 - z_v $$
$$ d_{ut} \geq z_u $$
Since we are minimizing $\sum d_{uv} c_{uv}$ and $c_{uv} &gt; 0$, this means that we want to minimize each individual $d_{uv}$, and so in fact
$$ d_{uv} = |z_u - z_v| $$
$$ d_{sv} = 1 - z_v $$
$$ d_{ut} = z_u $$
If we put $z_s = 1$ and $z_t = 0$, then the formula
$$ d_{uv} = |z_u - z_v| $$
holds for all $u,v$.
We can think of $z_v$ as specifying the position of the vertices on the real line. We are penalized $c_{uv} |z_u - z_v|$ for each edge $(u,v)$. Furthermore, $z_s = 1$ and $z_t = 0$. From this description, it is evident that there is no reason to put any vertex beyond the interval $[0,1]$.
If $z_v \in \{0,1\}$ for all $v$, then we can think of the $z_v$ as specifying a cut: one side (which includes $s$) consists of all $v$ such that $z_v = 1$, and the other side (which includes $t$) consists of all $v$ such that $z_v = 0$. If we allow general $z_v \in [0,1]$, then we can think of it as a &quot;fractional cut&quot;.
It is natural to ask whether fractional cuts are better than cuts. It turns out that they aren't. The simplest way to see this (same proof as in Luca Trevisan's lecture notes) is to construct the cut randomly: choose a threshold uniformly at random in $[0,1]$, and use it to partition the vertices into those left of the threshold and those right of the threshold. The probability that two vertices $u,v$ are in different sides of the cut is exactly $|z_u - z_v|$, and so the expected weight of the cut is $\sum_{uv} c_{uv} |z_u - z_v|$.
This is a very simple example of the metric method in the design of algorithms.