According to this we can do so by replacing every edge in the undirected graph with two edges backwards and forwards with the same capacity. But I'm having a hard time seeing how this prevents something like $f((u,v))=c$ and $f((v,u))=c$ (where c is the capacity in the original undirected edge) but then that means the original graph has flow $2c$. Could someone prove or explain why the capacity restrictions are still satisfied?
1 Answer
What you describe can happen in a feasible flow. However the net flow across the (undirected) edge $\{u,v\}$ would be $0$. Also, you say that the original graph has flow $2c$, this is false since the amount of flow from a vertex $s$ to a vertex $t$ in a graph is not the sum of the flows across all the edges, but rather the amount of flow leaving $s$ or, equivalently, entering in $t$.