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?
Why is one traversal sufficient for the Kuhn's maximal matching problem algorithm?
graphs;bipartite matching
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.How do we know that Kuhn's algorithm maintains the invariant? We prove it when we prove that Kuhn's algorithm is correct. I encourage you to find a correctness proof of the algorithm (such proofs are surely not too hard to find online) and read it.