= Solution
For every <perfect matching> $M$, each <vertex> occurs exactly once, so the feasibility inequalities give
$$
\sum_{e\in M}c_e\ge\sum_{\{u,v\}\in M}(x_u+x_v)=\sum_{v\in V}x_v.
$$
If a <perfect matching> $M^*$ uses only tight <edges>, equality holds. It therefore attains a lower bound valid for every <perfect matching>, proving \b[minimum cost]. In a <bipartite graph> this is the <weak duality> and <complementary slackness> certificate for the <assignment problem>. The <Hungarian algorithm> maintains feasible row and column potentials and seeks a <perfect matching> among tight <edges>.
Back to article page
