The Hungarian method finds a perfect matching and a potential such that the matching cost equals the potential value. This proves that both of them are optimal. In fact, the Hungarian method finds a perfect matching of tight edges: an edge ij is called tight for a potential if y(i)+y(j) = c(i, j). Let us denote the subgraph of tight edges by G_y. The cost of a perfect matching in G_y (if there is one) equals the value of .
