In the network flow problem, I'm trying to prove the following statement: $f'$ is an unique maximum flow if and only if the residual graph $G_{f'}$ is a directed acyclic graph.
For the forward direction, I will use contrapositive. If residual graph $G_{f'}$ has a cycle, then we can push flow along the cycle in $G_{f'}$, and augment the flow in the original graph $G$ Since sending flow or subtracting flow along cycle does not change the total flow of $f'$, so we have a different flow, say $f''$ with same flow value, which is $val(f') =val(f'')$.
Conversely, suppose $f'$ and $f''$ are both max flow, then I want to prove the residual graph $ G_{f''}$ has a cycle. Consider $f' -f''$ in $G_{f''}$, but I was wondering why $f'-f''$ will give a cycle in $G_{f''}$?
Can I get some help for the converse direction?
I was just considering this problem, and I finally solved it, so I thought to leave an answer in case it is useful for someone later on.
We will prove that if $G_f$ is acyclic (on edges with positive capacity in $G$), then $f$ is a unique maximum flow. Suppose $f, f'$ are two maximum flows. Now consider the following flow $d$:
$$\forall (u,v) \in E, \text{ if }f(u,v)\leq f'(u,v) \implies d(u,v)=f'(u,v)-f(u,v) \quad f(v,u) =0$$
$$\forall (u,v)\in E, \text{ if } f(u,v)>f'(u,v) \implies d(v,u)=f(u,v)-f'(u,v) \quad f(u,v)=0$$
Verify that $d$ is a feasible flow in $G_f$ (be careful that the flow is feasible in $G_f$, not $G$!) using the definition of $d$ and feasability of $f, f'$ (I'll leave the details for you).
Since $d$ is a feasible flow in $G_f$, then $f+d$ is a feasible flow of $G$. However, $f$ is a maximum flow, which implies that $|d|=0$. Since $G_f$ is acyclic, then $f$ cannot be a circulation (flow with zero flow that is just a cycle), which implies that $\forall (u,v): d(u,v)=0$. Which means that $f(u,v)=f'(u,v) \forall (u,v)$. So $f$ is unique.