5.1.1.2. Correctness of Ford-Fulkerson

Assume for now that the algorithm chooses augmenting paths so that its termination is guaranteed. Then the first step towards establishing the correctness of the MaxFlow procedure is to prove that each application of the Augment procedure maintains that the current flow is a feasible \(st\)-flow. Since the initial flow chosen by the MaxFlow procedure is feasible and we update the flow only by calling Augment, this ensures that the final flow returned by MaxFlow is a feasible \(st\)-flow.

Lemma 5.1: If \(f\) is a feasible \(st\)-flow in \(G\), then so is the flow \(f'\) returned by \(\boldsymbol{\textbf{Augment}(G, u, f, P)}\).

Proof: Let \(f^\delta = f' - f\), that is, for every pair of vertices \(x, y \in V\), we have

\[f^\delta_{x,y} = f'_{x,y} - f_{x,y}.\]

It's okay if theses values are negative; there is no expectation that \(f^\delta\) is a valid flow. Then

\[f^\delta_{x,y} = \begin{cases} \max\bigl(0, \delta - f_{y,x}\bigr) & \text{if } (x, y) \in P\\ -\min\bigl(\delta, f_{x, y}\bigr) & \text{if } (y, x) \in P\\ 0 & \text{otherwise.} \end{cases}\]

Since \(f\) is a valid flow, and thus satisfies flow conservation, and \(f' = f + f^\delta\), it suffices to prove that \(f^\delta\) satisfies flow conservation, in order to prove that \(f'\) satisfies flow conservation. In other words, we need to prove that

\[\sum_{y \in V} \left(f^\delta_{x,y} - f^\delta_{y,x}\right) = 0 \quad \forall x \in V \setminus \{s, t\}.\tag{5.1}\]

To prove (5.1) for all \(x \notin P\), observe that \(f^\delta_{x,y} = f^\delta_{y,x} = 0\) for all \(x \notin P\) and all \(y \in V\) because \((x, y), (y, x) \notin P\) if \(x \notin P\).

To prove (5.1) for all \(x \in P \setminus \{s, t\}\), let \(y\) be \(x\)'s predecessor in \(P\) and let \(z\) be \(x\)'s successor in \(P\). Then

\[\begin{aligned} f^\delta_{y,x} &= \max\bigl(0, \delta - f_{x, y}\bigr),\\ f^\delta_{x,y} &= -\min\bigl(\delta, f_{x, y}\bigr),\\ f^\delta_{x,z} &= \max\bigl(0, \delta - f_{z, x}\bigr),\\ f^\delta_{z,x} &= -\min\bigl(\delta, f_{z, x}\bigr),\text{ and}\\ f^\delta_{x,v} &= f^\delta_{v,x} = 0 \quad \forall v \notin \{y, z\}. \end{aligned}\]

Thus,

\[\begin{aligned} \sum_{v \in V} \left(f^\delta_{x,v} - f^\delta_{v,x}\right) &= f^\delta_{x,y} + f^\delta_{x,z} - f^\delta_{y,x} - f^\delta_{z,x}\\ &= -\min\bigl(\delta, f_{x,y}\bigr) - \max\bigl(0, \delta - f_{x,y}\bigr) + \max\bigl(0, \delta - f_{z,x}\bigr) + \min\bigl(\delta, f_{z,x}\bigr)\\ &= -\delta + \delta\\ &= 0. \end{aligned}\]

To prove that \(f'\) respects the capacity constraints, consider any pair of vertices \((x, y)\).

If \((x,y) \notin P\) and \((y,x) \notin P\), then \(0 \le f'_{x,y} = f_{x,y} \le u_{x,y}\) because \(f\) is a feasible \(st\)-flow.

If \((x,y) \in P\), then

\[0 \le \rlap{f_{y,x} - \min\bigl(\delta, f_{y,x}\bigr) \le f_{y,x} \le u_{y,x}}\phantom{\max\bigl(f_{x,y}, f_{x,y} + u_{x,y} - f_{x,y} + f_{y,x} - f_{y,x}\bigr)}\]

and

\[\begin{aligned} 0 &\le f_{x,y} \le f_{x,y} + \max\bigl(0, \delta - f_{y,x}\bigr)\\ &\le \max\bigl(f_{x,y}, f_{x,y} + u_{x,y} - f_{x,y} + f_{y,x} - f_{y,x}\bigr)\\ &= \max\bigl(f_{x,y}, u_{x,y}\bigr)\\ &= u_{x,y} \end{aligned}\]

because \(f\) is a feasible \(st\)-flow and \(\delta > 0\). Since \(f'_{x,y} = f_{x,y} + \max\bigl(0, \delta - f_{y,x}\bigr)\) and \(f'_{y,x} = f_{y,x} - \min\bigl(\delta,f_{y,x}\bigr)\), this shows that \(0 \le f'_{x,y} \le u_{x,y}\) and \(0 \le f'_{y,x} \le u_{y,x}\). Thus, \(f'\) satisfies the capacity constraints. Since it also satisfies flow conservation, \(f'\) is a feasible \(st\)-flow. ▨

Since the \(st\)-flow \(f'\) returned by Augment is feasible and sends more flow from \(s\) to \(t\) than \(f\)—\(F'_s > F_s\)—we conclude that as long as there exists an augmenting path in \(G^f\), \(f\) cannot be a maximum flow. Here is the contrapositive of this statement:

Observation 5.2: If \(f\) is a maximum \(st\)-flow in \(G\), then there exists no augmenting path from \(s\) to \(t\).

Since MaxFlow returns once there is no augmenting path in \(G^f\), to complete the correctness proof of MaxFlow, we need to prove the converse of this corollary: If there exists no augmenting path from \(s\) to \(t\) in \(G^f\), then \(f\) is a maximum \(st\)-flow. Our tool to do this is the Max-Flow Min-Cut Theorem, discussed next.