# Why is one traversal sufficient for the Kuhn's maximal matching problem algorithm?

In Kuhn's algorithm for the maximum bipartite matching problem we iterate through the vertices of one partite set and try to build the increasing chain, starting with the current vertex. Once the traversal is completed, we claim that the maximal matching is found. But why don't we need to check again the vertices for which we weren't able to build the increasing chain? How can we prove that if for some vertex v it was not possible to build the increasing chain starting with v during the traversal, then we don't need to check v again? Why shouldn't we perform the second traversal?

• Have you seen a proof of correctness for the algorithm? – Yuval Filmus May 11 '15 at 3:14

Kuhn's algorithm maintains the following invariant: after scanning through vertices $v_1,\ldots,v_k$ on the left, the current matching is a maximal matching of the graph consisting of $v_1,\ldots,v_k$ on the left, and the entire right-hand side. Hence at the end, we get a maximal matching of the entire graph.