So the wikipedia page gives the following linear programs for max-flow, and the dual program :

While it is quite straight forward to see that the max-flow linear program indeed computes a maximum flow (every feasable solution is a flow, and every flow is a feasable solution), i couldn’t find convincing proof that the dual of the max-flow linear program indeed is the LP of the min-cut problem.

An ‘intuitive’ proof is given on wikipedia, namely : $d_{uv}$ is 1 if the edge $(u,v)$ is counted in the cut and else $0$, $z_u$ is $1$ if $u$ is in the same side than $s$ in the cut, and $0$ if $u$ is in the same side of the cut than $t$

But that doesn’t convince me a lot, mainly why should all the variables be integers, while we don’t have integer conditions ?

And in general, do you have a convincing proof that the dual of the max-flow LP indeed is the LP formulation for min-cut ?

**Edit** : Ok i found a proof here http://theory.stanford.edu/~trevisan/cs261/lecture15.pdf , however it only gives a probabilistic way to build the cut from the variables assignement of the LP.