structural:scholar_edition
Proof that y remains a potential

To show that y remains a potential after being adjusted, it suffices to show that no edge has its total potential increased beyond its cost. This is already established for edges in M by the preceding paragraph, so consider an arbitrary edge uv from S to T. If y (u) {\displaystyle y(u)} is increased by Δ, then either v ∈ Z ∩ T {\displaystyle v\in Z\cap T}, in which case y (v) {\displaystyle y(v)} is decreased by Δ, leaving the total potential of the edge unchanged, or v ∈ T ∖ Z {\displaystyle v\in T\setminus Z}, in which case the definition of Δ guarantees that y (u) + y (v) + Δ ≤ c (u, v) {\displaystyle y(u)+y(v)+\Delta \leq c(u,v)}. Thus y remains a potential.