Show that the MINIMUM CUT PROBLEM is the dual program of the MAXIMUM FLOW PROBLEM
Let $(G=(V,E), s,t,c)$ be a network.
Let consider problem (4.1) maximize $\sum_{v: (s,v) \in E} f(s,v)$ with constraints $\sum_{u:(u,v) \in E} f(u,v) = \sum_{w : (v,w) \in E} f(v,w)$ for all $v \in V-\{s,t\}$, $f(u,v) \leq c(u,v)$ for all $(u,v) \in E$ and $f(u,v) \geq 0 $ for all $(u,v) \in E$.
Let $P$ be a set of all paths from $s$ to $t$ and construct problem (4.2) maximize $\sum_{p\in P} x_p$ with $\sum_{p\in P:(u,v) \in P}x_p \leq c(u,v)$ for all $(u,v) \in E$ and for all $p\in P$, and $x_p \geq 0 $ for all $p \in P$.
I will neither prove nor present Flow Decomposition theorem, but I believe it is true, by this theorem, the assumption (4.1) has feasible solution implies (4.2) has feasible solution and they have the same cost.
Suppose that $x_p$ is feasible solution for (4.2), then $f(u,v):=\sum_{p \in P:(u,v) \in P}x_p$ is a feasible solution of (4.1) and $\sum_{v:(u,v)\in E} f(u,v) = \sum_{p\in P: v \in p} x_p = \sum_{w : (v,w) \in E} f(v,w)$.
Therefore (4.1) and (4.2) are equivalent.
(4.2) has dual problem (4.3) minimize $\sum_{(u,v) \in E} c(u,v) y_{u,v} $ with constraitns $\sum_{(u,v) \in P} y_{u,v} \geq 1$ for all $p \in P, y_{u,v} \geq 0 $ for all $(u,v) \in E$.
$y_v$ can be defined as $\sum_{(v,w) \in E} y_{v,w}$.
Then (4.3) has form minimize $\sum_{(u,v) \in E} c(u,v) y_{u,v}$ subject to $y_v + y+s_v \geq 1 $ for all $v $ such that $(s,v) \in F$, $y_v-y_u+y_{u,v} \geq 0$ for all $(u,v) \in E$ with $u\neq s, v\neq t$, $-y_u+y_{u,t} \geq 0 $ for all $u$ with $(u,t) \in E$.