[proofplan] We compare $f'$ with $f$ through the edge perturbation induced by the residual path. The bottleneck definition gives exactly the inequalities needed to keep every updated edge between $0$ and its capacity. Conservation is checked vertex by vertex: along the residual path, each internal vertex receives one signed contribution of size $\Delta$ and sends one signed contribution of size $\Delta$, so its net balance is unchanged. At the source the net outflow increases by $\Delta$, hence the flow value increases by $\Delta$. [/proofplan] [step:Encode the augmentation as a signed edge perturbation] For each edge $e \in E$, define the signed perturbation $\delta(e) \in \{-\Delta,0,\Delta\}$ as follows. Set $\delta(e)=\Delta$ if $(\operatorname{tail}(e),\operatorname{head}(e),e,+)$ occurs in $P$. Set $\delta(e)=-\Delta$ if $(\operatorname{head}(e),\operatorname{tail}(e),e,-)$ occurs in $P$. Set $\delta(e)=0$ if no residual arc of $P$ is tagged by $e$. These cases are mutually exclusive. Indeed, if both residual arcs tagged by the same original edge $e$ occurred in the simple directed path $P$, then the path would pass through both endpoints of $e$ in one direction and later pass through the same two endpoints in the opposite direction, forcing at least one endpoint of $e$ to be visited twice. Hence each original edge tag contributes at most one update in this definition. The definition of $f'$ is therefore exactly: for every $e \in E$, $f'(e)=f(e)+\delta(e)$. [/step] [step:Use the bottleneck inequality to preserve capacity constraints] Let $e \in E$. If $\delta(e)=0$, then $f'(e)=f(e)$, so $0 \leq f'(e)\leq c(e)$ because $f$ is feasible. If $\delta(e)=\Delta$, then the forward residual arc tagged by $e$ occurs in $P$. Its residual capacity is $c(e)-f(e)$, so the definition of $\Delta$ and the positivity of the bottleneck give $0 < \Delta \leq c(e)-f(e)$. Since $f$ is feasible, $0 \leq f(e)$; adding $\Delta$ and using the preceding inequality yields $0 \leq f(e) \leq f(e)+\Delta \leq c(e)$. Hence $0 \leq f'(e)\leq c(e)$. If $\delta(e)=-\Delta$, then the reverse residual arc tagged by $e$ occurs in $P$. Its residual capacity is $f(e)$, so the definition of $\Delta$ gives $0 < \Delta \leq f(e)$. Therefore subtracting $\Delta$ does not make the flow negative, and feasibility of $f$ gives $0 \leq f(e)-\Delta \leq f(e) \leq c(e)$. Again $0 \leq f'(e)\leq c(e)$. [guided] Fix an original edge $e \in E$. We must prove that the updated value $f'(e)$ is still a legal amount of flow on $e$, meaning it lies between $0$ and $c(e)$. There are three cases. If the residual path $P$ does not use any residual arc tagged by $e$, then $\delta(e)=0$ and $f'(e)=f(e)$. Since $f$ is feasible, this gives \begin{align*} 0 \leq f'(e)=f(e)\leq c(e). \end{align*} Suppose next that $P$ uses the forward residual arc tagged by $e$. This arc exists precisely because more flow may still be pushed along $e$, and its residual capacity is $c(e)-f(e)$. Since $\Delta$ is the minimum residual capacity among all arcs of $P$, and since the statement now records that the bottleneck is positive, we have $0 < \Delta \leq c(e)-f(e)$. Adding $f(e)$ to the right inequality gives $f(e)+\Delta \leq c(e)$. The lower bound follows from $f(e)\geq 0$ and $\Delta>0$, so $0 \leq f(e) \leq f(e)+\Delta \leq c(e)$. Since $f'(e)=f(e)+\Delta$ in this case, the capacity constraint is preserved. Finally suppose that $P$ uses the reverse residual arc tagged by $e$. This means the augmentation cancels $\Delta$ units of the old flow on $e$. The residual capacity of this reverse arc is $f(e)$, and again the bottleneck definition gives $0 < \Delta \leq f(e)$. Subtracting $\Delta$ from $f(e)$ therefore cannot make the flow negative, so $0 \leq f(e)-\Delta$. The upper bound is inherited from feasibility of $f$: $f(e)-\Delta \leq f(e)\leq c(e)$. Thus $0 \leq f'(e)=f(e)-\Delta \leq c(e)$. In every case, $f'$ satisfies the edge capacity constraint on $e$. [/guided] [/step] [step:Express conservation in terms of net signed outflow] For a vertex $x \in V$, define the net flow balance of a flow $h:E \to [0,\infty)$ at $x$ to be the total $h$-flow on edges whose tail is $x$ minus the total $h$-flow on edges whose head is $x$. Denote this number by $B_h(x)$. For the perturbation $\delta:E \to \mathbb{R}$, define $B_\delta(x)$ analogously as the total $\delta$-contribution on edges whose tail is $x$ minus the total $\delta$-contribution on edges whose head is $x$. By linearity of finite sums, \begin{align*} B_{f'}(x)=B_f(x)+B_\delta(x) \quad \text{for every } x \in V. \end{align*} Thus it remains to compute $B_\delta(x)$. [/step] [step:Show that the signed perturbation cancels at every internal vertex] Let $x \in V \setminus \{s,t\}$. If $x$ is not a vertex of the path $P$, then no residual arc of $P$ enters or leaves $x$, so every edge contribution to $B_\delta(x)$ is zero and $B_\delta(x)=0$. Now suppose $x=u_j$ for some $1 \leq j \leq m-1$. The path has exactly one residual arc entering $x$, namely $r_j=(u_{j-1},x,e_j,\sigma_j)$, and exactly one residual arc leaving $x$, namely $r_{j+1}=(x,u_{j+1},e_{j+1},\sigma_{j+1})$. An entering forward residual arc increases inflow at $x$ by $\Delta$, while an entering reverse residual arc decreases outflow from $x$ by $\Delta$; in both cases it contributes $-\Delta$ to $B_\delta(x)$. A leaving forward residual arc increases outflow from $x$ by $\Delta$, while a leaving reverse residual arc decreases inflow into $x$ by $\Delta$; in both cases it contributes $+\Delta$ to $B_\delta(x)$. Therefore \begin{align*} B_\delta(x)=(-\Delta)+\Delta=0. \end{align*} Since $f$ is feasible, $B_f(x)=0$ for every $x \in V\setminus\{s,t\}$. Hence \begin{align*} B_{f'}(x)=B_f(x)+B_\delta(x)=0. \end{align*} So $f'$ satisfies flow conservation at every internal vertex. [guided] Fix an internal vertex $x \in V\setminus\{s,t\}$. The goal is to show that the augmentation does not create or destroy flow at $x$. If $x$ is not on the residual path $P$, then no residual arc of $P$ enters or leaves $x$, so no edge incident with $x$ receives a nonzero signed perturbation in the balance $B_\delta(x)$. Hence $B_\delta(x)=0$. Now suppose $x=u_j$ for some $1 \leq j \leq m-1$. Because $P$ is a simple directed path, exactly one residual arc of $P$ enters $x$, namely $r_j=(u_{j-1},x,e_j,\sigma_j)$, and exactly one residual arc leaves $x$, namely $r_{j+1}=(x,u_{j+1},e_{j+1},\sigma_{j+1})$. We compute their effects on net signed outflow. An entering forward residual arc increases inflow at $x$ by $\Delta$, while an entering reverse residual arc decreases outflow from $x$ by $\Delta$; both changes contribute $-\Delta$ to $B_\delta(x)$. A leaving forward residual arc increases outflow from $x$ by $\Delta$, while a leaving reverse residual arc decreases inflow into $x$ by $\Delta$; both changes contribute $+\Delta$ to $B_\delta(x)$. Therefore \begin{align*} B_\delta(x)=(-\Delta)+\Delta=0. \end{align*} Since $f$ is feasible, it satisfies flow conservation at every internal vertex, so $B_f(x)=0$. By the finite-sum identity $B_{f'}(x)=B_f(x)+B_\delta(x)$, we obtain \begin{align*} B_{f'}(x)=0+0=0. \end{align*} Thus $f'$ satisfies flow conservation at $x$. [/guided] [/step] [step:Compute the change in value at the source] The first residual arc of the path is $r_1=(s,u_1,e_1,\sigma_1)$. Because $P$ is a simple directed path from $s$ to $t$, no residual arc of $P$ other than $r_1$ is incident with $s$; otherwise $s$ would be visited again after the initial vertex. If $\sigma_1=+$, then $e_1$ has tail $s$, and the augmentation increases the outflow from $s$ by $\Delta$. If $\sigma_1=-$, then $e_1$ has head $s$, and the augmentation decreases the inflow into $s$ by $\Delta$. In either case, \begin{align*} B_\delta(s)=\Delta. \end{align*} Therefore \begin{align*} |f'|=B_{f'}(s)=B_f(s)+B_\delta(s)=|f|+\Delta. \end{align*} Together with the capacity constraints and conservation already proved, this shows that $f'$ is feasible and has value $|f|+\Delta$. [guided] The value of a flow is measured by net outflow from the source, so we compute the perturbation balance at $s$. The first residual arc of the path is $r_1=(s,u_1,e_1,\sigma_1)$. Since $P$ is a simple directed path from $s$ to $t$ and $s\neq t$, the source appears only as the initial vertex of the path; if another residual arc of $P$ were incident with $s$, then the path would revisit $s$ after starting there. There are two possible signs for the first residual arc. If $\sigma_1=+$, then $e_1$ has tail $s$, and adding $\Delta$ to $f(e_1)$ increases the outflow from $s$ by $\Delta$. If $\sigma_1=-$, then $e_1$ has head $s$, and subtracting $\Delta$ from $f(e_1)$ decreases the inflow into $s$ by $\Delta$. Both operations increase net outflow from $s$ by exactly $\Delta$, so \begin{align*} B_\delta(s)=\Delta. \end{align*} Using the balance identity from the earlier step, we get \begin{align*} |f'|=B_{f'}(s)=B_f(s)+B_\delta(s)=|f|+\Delta. \end{align*} The preceding steps proved all capacity constraints and all internal conservation laws, so $f'$ is a feasible flow with value $|f|+\Delta$. [/guided] [/step]