Proving that max flows of undirected graph and equivalent directed graph are equal

Question

There is an undirected graph $G$. A graph $H$ is constructed by changing each edge $(a,b)$ in $G$ to a pair of directed edges $(a,b)$ and $(b,a)$. How to prove that the maximum flow in $H$ is equal to the maximum flow in $G$?

I don't really have any idea how to start it. I just know that I can use Ford-Fulkerson on $H$ and update the reverse edge such that $f(a,b)+f(b,a)=c(a,b)$ but that's it.

Answer 1

If $f_G$ is a valid flow for $G$, then there exists a valid flow $f_H$ for $H$ such that $|f_G| = |f_H|$. This is true since there is always a flow $f'_G$ for $G$ such that $|f'_G| = |f_G|$ and no edge is traversed in both directions in a flow decomposition of $f'_G$. If some edge $(u,v)$ is traversed by $x$ units of flow from $u$ to $v$ and $y \le x$ units of flow from $v$ to $u$ then you could redefine the flow to only send $x-y$ units of flow from $u$ to $v$. If $(u,v)$ is used from $u$ to $v$ you can then define $f_H(u,v) = f'_G(u,v)$ and $f_H(v,u)=0$. (If $(u,v)$ is unused then $f_H(u,v) = f_H(v,u) = 0$).

If $f_H$ is a valid flow for $H$, then there exists a valid flow $f_G$ for $G$ such that $|f_H| = |f_G|$. Notice that if $f_H$ uses both $(u,v)$ and $(v,u)$ (assume w.l.o.g., that $f_H(u,v) \ge f_H(v,u)$) then the flow $f'_H$ defined by $f'_H(u,v) = f_H(u,v) - f_H(v,u)$, $f'_H(v,u)=0$, and $f'_H(x,y) = f_H(x,y)$ for $(x,y) \not\in \{ (u,v), (v,u) \}$ is also a valid flow for $H$ and $|f'_H| = |f_H|$. This shows that you can define $f_G(u,v) = f'_H(u,v)$.