Past exam of the Probability, statistics and options II course of the University of Oxford / 2007 / S / 4 / c

Before a potential update, let $S$ be the reached rows and $T$ the reached columns in an alternating forest grown from unmatched rows. Every reached column is matched, or an augmentation would already have occurred, and its matched row is reached. Each tree has one more reached row than reached column, so $|S|-|T|>0$.

The update amount is the smallest slack across $S\times T^c$. It is strictly positive because all zero-slack edges have already been explored, and the complete assignment problem guarantees that the set is nonempty before a perfect matching is found. Increasing $u_i$ for $i\in S$ and decreasing $v_j$ for $j\in T$ therefore increases the dual sum byAll feasibility inequalities remain valid by the definition of the minimum slack.