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

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.

## 1 Answer

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)$$.