The Hungarian Algorithm In reading the proof of the Hungarian algorithm for the assignment problem in a weighted bigraph, I could not understand why the algorithm terminates. In the algorithm we choose a cover (namely labels for the vertices of the bigraph: $u_1\cdots u_n$, $v_1,\cdots v_n$ with $u_i+v_j\ge $weight of an edge $x_iy_j\forall i,j$) and keep adjusting it until the equality subgraph (the spanning subgraph of $K_{n,n}$ whose edges are pairs $x_iy_j$ such that $u_i+v_j=$weight of $x_iy_j$) has a perfect matching. My question is after each adjustment, why does the cost of the cover $\sum(u_i+v_i)$ reduce?
(We assume the weights are all integers).
Thanks.

Let $\mathrm{M}$ be a maximum matching in the equality subgraph. According to König's theorem, we can find a vertex cover $C$ such that $\mathrm{|M|}=|C|$. We Call $R$ the set $C\cap X$, and $T$ the set $C\cap Y$.
Now, either $\mathrm{M}$ is a perfect matching, which means the algorithm should stop and return our current labelling as optimal, or $X$ is not saturated by $\mathrm{M}$. In that case, we adjust the weighted cover : We define $\epsilon = \min\{(u_i+v_j-w(x_iy_j):x_i\notin R, y_j \notin T\}$, and we substract $\epsilon$ to $u_i$ for each $x_i \notin R$, and we add $\epsilon$ to each $y_j$ for each $y_j \in T$.
The cost of the cover changes by $(|T| - |X\setminus R|)\epsilon$. This change is strictly negative because $|R|+|T|=|\mathrm{M}|\lt |X| \Rightarrow |T| \lt |X|-|R| \Rightarrow |T| \lt |X \setminus R|$. Since we assumed the integrality of the labels, it ensures that the algorithm terminates in finitely many steps.
