[Oops.] Show new flow is well-defined in the maxflow-mincut theorem proof

[acou12]

Please verify that the error is present in the most recent revision before reporting. Yep

Chapter number or note title: 10.3, The Maxflow-Mincut Theorem

Page number: 332

Error description: The new function constructed using the augmenting path, $f'$, is referred to as a flow, but it is never actually shown that it satisfies the conservation constraint (defined on page 328), which seems like a fairly important step in the proof and is not obvious.

Suggested fix (if any): Justify the fact that $f'$ is a flow. A justification could look something like this:

We only need to consider the conservation constraint with respect to verticies that lie in the augmenting path $P$, since the other verticies' edges have not been modified. Let $v$ be some vertex in $P$ that is not $s$ or $t$ (the two execptions to the conservation constraint). There must be verticies that came before and after $v$ in $P$; call them $u$ and $w$, respectively, so that $u \to v \in P$ and $v \to w \in P$. There must be an edge that connect $u$ and $v$; that is, one of the following holds:

• $u \to v \in E$: In this case, we have $f'(u \to v) = f(u \to v) + F$, so the inflow has increased by $F$.
• $v \to u \in E$: Here, $f'(v \to u) = f(v \to u) - F$, so the outflow has decreased by $F$, or equivalently, the inflow has increased by $F$.

In either case, the total flow into $v$ has increased by $F$ due to the edge. Similarly for $v$ and $w$, we can show that the total flow out of $v$ has decreased by $F$ due to the edge, so considered together there is no total change in inflow or outflow. Since $P$ only contains $v$ at most once, these are the only two edges that could have been modified by augmentation. So, because $f$ satisfies the conservation constraint by assumption, so does $f'$.