 Solution

Begin with $u=v=0$ and the printed matching $\{(1,1),(3,2),(5,3)\}$. Grow an alternating tree from unmatched row two. Its tight edge reaches column two, whose matched row is three. Thus the reached row set is $S=\{2,3\}$ and the reached column set is $T=\{2\}$. Among unreached columns the reduced costs are $(6,5,4,4)$ from row two and $(3,4,2,3)$ from row three, so their minimum is two.

Increase $u_2,u_3$ by two and decrease $v_2$ by two. The new tight edge $(3,4)$ reaches an unmatched column. Augment along $2\to 2\to 3\to 4$, replacing $(3,2)$ by $(2,2),(3,4)$. The matching becomes $\{(1,1),(2,2),(3,4),(5,3)\}$.

Now grow from unmatched row four. Edge $(4,1)$ reaches matched row one, and edge $(1,5)$ reaches unmatched column five. Augment along $4\to 1\to 1\to 5$, replacing $(1,1)$ by $(4,1),(1,5)$. This yieldsNo further potential update is needed. The final potentials are $u=(0,2,2,0,0)$ and $v=(0,-2,0,0,0)$. Their reduced-cost matrix isEvery entry is nonnegative and every chosen entry is zero. The dual sum is $\sum u_i+\sum v_j=2$, so part (a) certifies optimality.