 Solution

For every perfect matching $M$, each vertex occurs exactly once, so the feasibility inequalities giveIf a perfect matching $M^{\ast }$ uses only tight edges, equality holds. It therefore attains a lower bound valid for every perfect matching, proving 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.