Proof that if the residual network of a max flow has no cycles then the max flow is unique

Question

Let $G = (V,E)$ be a directed graph with source $s$ and sink $t$ and $s \neq t$. For each edge $e \in E$, we have $c(e) \in \Bbb N$.

After running Ford-Fulkerson algorithm a flow function $f$ returned a max flow.

Let $R_f$ be the residual network that represents the max-flow $f$.

I would like to prove that if $R_f$ has no cycles then there is no other max flow function. I tried assuming that $R_f$ has no cycle and assuming towards contradiction that another flow function exists but I was stuck trying to find a cycle, thus reaching the contradiction. Any help will be appreciated.

Answer 1

Suppose there is a max-flow $f'\neq f$. Then,

1. 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.
2. 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-zero flow repeatedly. That following action is always possible since

• we will never encounter the source nor the sink since this is a $0$-valued flow, and
• for any vertex that is not source nor sink, the sum of outgoing flow value from that vertex is equal to the sum of incoming flow values to that vertex.

Since there are finitely many vertexes, we will go back to some vertex that we have visited before, at which time we have found a cycle.

---

Exercise 1. Verify point 1.

Exercise 2. Prove that we can decompose a $0$-valued flow into at most $m$ cycle flows, where $m$ is the number of edges excluding the edges from the source and the edges to the sink. (A cycle flow is a flow where the flow function is zero everywhere except on all edges of one cycle.)