[proofplan] We argue by contradiction and choose, among all vertices whose distance decreases after the augmentation, one with minimum new distance. Looking at the last arc on a new shortest path to that vertex, either the arc was already present before augmentation or it was newly created. The first case contradicts the minimal choice of the vertex, while the second case uses the fact that a newly created residual arc is the reverse of an arc used on the old shortest augmenting path, forcing the old distance relation in the opposite direction. Both cases contradict the assumed decrease. [/proofplan] [step:Choose a closest vertex whose residual distance decreases] Let $G_f=(V,E_f)$ and $G_{f'}=(V,E_{f'})$ be the [residual directed graphs](/page/Residual%20Network) before and after augmentation. For a directed arc $a \in V \times V$, write $\operatorname{tail}(a)$ and $\operatorname{head}(a)$ for its tail and head. Suppose, for contradiction, that there exists a vertex $w \in V$ such that \begin{align*} d_{f'}(w) < d_f(w). \end{align*} Then $d_{f'}(w)<\infty$, so $w$ is reachable from $s$ in $G_{f'}$. Among all such vertices, choose $v \in V$ with $d_{f'}(v)$ minimal. Since $d_f(s)=d_{f'}(s)=0$, we have $v \neq s$, and therefore $d_{f'}(v) \geq 1$. Let \begin{align*} Q=(v_0,v_1,\dots,v_k) \end{align*} be a shortest directed path from $s$ to $v$ in $G_{f'}$, where $v_0=s$, $v_k=v$, and $k=d_{f'}(v)$. Define $u:=v_{k-1}$ and define the last arc \begin{align*} a:=(u,v) \in E_{f'}. \end{align*} The initial segment $(v_0,\dots,v_{k-1})$ is a shortest directed path from $s$ to $u$ in $G_{f'}$; otherwise, replacing it by a shorter path would produce a shorter directed path from $s$ to $v$. Hence \begin{align*} d_{f'}(u)=k-1=d_{f'}(v)-1. \end{align*} By the minimal choice of $v$, the vertex $u$ does not have decreased distance, because $d_{f'}(u)<d_{f'}(v)$. Thus \begin{align*} d_{f'}(u) \geq d_f(u). \end{align*} [guided] Assume that some residual distance decreases after the augmentation. We choose a counterexample with the smallest new distance because then every predecessor on a new shortest path has already been ruled out as a counterexample. Formally, suppose there is $w \in V$ such that \begin{align*} d_{f'}(w) < d_f(w). \end{align*} Since the left-hand side is smaller than $d_f(w)$, it is finite, so $w$ is reachable from $s$ in the new residual graph $G_{f'}$. Choose $v$ among all vertices satisfying this strict inequality so that $d_{f'}(v)$ is minimal. The source cannot be such a vertex, since \begin{align*} d_f(s)=d_{f'}(s)=0. \end{align*} Therefore $v \neq s$. Let \begin{align*} Q=(v_0,v_1,\dots,v_k) \end{align*} be a shortest directed path from $s$ to $v$ in $G_{f'}$, with $v_0=s$, $v_k=v$, and $k=d_{f'}(v)$. Since $v \neq s$, we have $k \geq 1$. Define $u:=v_{k-1}$, so the final arc of $Q$ is \begin{align*} a:=(u,v) \in E_{f'}. \end{align*} The path $(v_0,\dots,v_{k-1})$ has length $k-1$ and reaches $u$. It must be shortest: if there were a shorter directed path from $s$ to $u$ in $G_{f'}$, appending the arc $(u,v)$ would give a directed path from $s$ to $v$ shorter than $Q$. Hence \begin{align*} d_{f'}(u)=k-1=d_{f'}(v)-1. \end{align*} Now $u$ has strictly smaller new distance than $v$. Since $v$ was chosen as the closest vertex whose distance decreases, $u$ cannot also have decreased distance. Therefore \begin{align*} d_{f'}(u) \geq d_f(u). \end{align*} This is the key use of the minimal-counterexample choice. [/guided] [/step] [step:Rule out the case where the last new shortest-path arc already existed] Assume first that $a=(u,v) \in E_f$. Since $a$ is a residual arc before augmentation, any shortest directed path from $s$ to $u$ in $G_f$, followed by $a$, gives a directed path from $s$ to $v$ in $G_f$ whenever $d_f(u)<\infty$. The inequality $d_{f'}(u)\geq d_f(u)$ and the finiteness of $d_{f'}(u)$ imply $d_f(u)<\infty$. Hence \begin{align*} d_f(v) \leq d_f(u)+1 \leq d_{f'}(u)+1=d_{f'}(v). \end{align*} This contradicts the defining property of $v$, namely $d_{f'}(v)<d_f(v)$. Therefore the final arc $a=(u,v)$ cannot have belonged to $E_f$. [/step] [step:Identify a newly created residual arc as the reverse of an old augmenting-path arc] Since $a=(u,v) \in E_{f'}$ but $a \notin E_f$, the arc $a$ was created by the augmentation. Let $c_f:V\times V\to [0,\infty)$ and $c_{f'}:V\times V\to [0,\infty)$ denote the [residual capacity](/page/Residual%20Capacity) functions before and after the augmentation, so $E_f=\{(x,y)\in V\times V:c_f(x,y)>0\}$ and $E_{f'}=\{(x,y)\in V\times V:c_{f'}(x,y)>0\}$. Let $P$ be the shortest directed $s$-$t$ path in $G_f$ used for the [augmentation](/page/Augmenting%20Path), and let $\delta>0$ be the augmentation amount. Under the standard residual-capacity update, for each directed arc $(x,y)$ of $P$, the forward residual capacity changes by $c_{f'}(x,y)=c_f(x,y)-\delta$ and the reverse residual capacity changes by $c_{f'}(y,x)=c_f(y,x)+\delta$; every ordered pair not equal to a forward arc or reverse arc associated to $P$ has unchanged residual capacity. Since $c_f(u,v)=0$ and $c_{f'}(u,v)>0$, the only possible source of the new residual capacity on $(u,v)$ is the reverse update coming from the arc $(v,u)$ on $P$. Therefore the old augmenting path $P$ contains the directed residual arc \begin{align*} (v,u) \in E_f. \end{align*} Because $P$ is a shortest directed path from $s$ to $t$ in $G_f$, every prefix of $P$ is a shortest directed path from $s$ to its endpoint in $G_f$. Indeed, if a prefix endpoint had a shorter directed path from $s$ in $G_f$, replacing that prefix in $P$ and keeping the remaining suffix of $P$ would produce a directed walk from $s$ to $t$ in $G_f$ with length strictly smaller than the length of $P$. If this walk repeats vertices, deleting directed cycles gives a directed path from $s$ to $t$ whose length is no larger than the walk length, hence still smaller than $P$, contradicting the choice of $P$ as a shortest augmenting path. The arc $(v,u)$ occurs on $P$, so the prefix of $P$ ending at $u$ is obtained from the prefix ending at $v$ by appending the single arc $(v,u)$. Hence \begin{align*} d_f(u)=d_f(v)+1. \end{align*} [/step] [step:Combine the old and new distance relations to get a contradiction] From the choice of $v$ we already have \begin{align*} d_{f'}(u)\geq d_f(u). \end{align*} Using the relation obtained from the old shortest augmenting path, \begin{align*} d_f(u)=d_f(v)+1. \end{align*} Using also the final arc of the new shortest path, \begin{align*} d_{f'}(v)=d_{f'}(u)+1. \end{align*} Combining these equalities and inequalities gives first \begin{align*} d_{f'}(v)=d_{f'}(u)+1. \end{align*} Since $d_{f'}(u)\geq d_f(u)$, this implies \begin{align*} d_{f'}(v)\geq d_f(u)+1. \end{align*} Substituting $d_f(u)=d_f(v)+1$ yields \begin{align*} d_{f'}(v)\geq d_f(v)+2. \end{align*} In particular, \begin{align*} d_{f'}(v)>d_f(v), \end{align*} which contradicts the assumption that $v$ was a vertex with decreased distance: \begin{align*} d_{f'}(v)<d_f(v). \end{align*} Both possible cases for the final arc $a$ lead to contradictions. Therefore no vertex has smaller residual distance after the augmentation, and for every $v \in V$, \begin{align*} d_{f'}(v)\geq d_f(v). \end{align*} This proves the monotonicity lemma. [/step]