Max-flow problem for networks with weighted vertices [closed]

Solution 1:

Thank you to Gerry Myerson for the suggestion. My proof was quite lengthy, but the abridged version is to first construct the new network G' as outlined above.

Then, we take $f$ to be a valid arbitrary flow of some size $m$ on $G$, and show that we can construct a valid flow $f'$ on $G'$ that has the same size. We repeat the other direction by taking $f'$ to be a valid arbitrary flow of some size $m$ on $G'$, and again show that we can construct a valid flow $f$ on $G$ with size $m$.

This shows that the size of the maximum flow on $G$ is equal to the max flow on $G'$. Hence, run Ford-Fulkerson on $G'$ to obtain the max-flow for $G$.