2

Suppose there is a max-flow $f'\neq f$. Then, The function $\Delta f= f'-f$ is a nontrivial flow of flow value $0$ in $R_f$. (Nontrivial just means $\Delta f$ is not zero on some edge. There is a cycle in a $0$-valued nontrivial flow. How do we prove point 2? Start with any edge with non-zero flow. Visit vertexes by following an outgoing edge with non-...


1

Here is a formal proof, thanks to your hint of the max-flow min-cut theorem. Let us treat $G$ directly as a network with capacity function $w$. Suppose we are given three arbitrary nodes $a, b, c$ in $V$. Select a minimum $a$-$c$ cut of $G$, $(S, T)$. Let $w(S,T)$ be the capacity of $(S,T)$ as a cut of $G$, i.e. $$w(S,T)=\sum_{u\in S, v\in T} w(u,v).$$ ...


Only top voted, non community-wiki answers of a minimum length are eligible