Berge's lemma

Berge's lemma states that in a bipartite graph, a maximum matching (the largest set of non-overlapping edges connecting two groups) can be characterized by the absence of certain alternating paths. Specifically, a matching is maximum if and only if there is no alternating path (a path that alternates between edges in and not in the matching) that starts and ends at unmatched vertices. This means that if you cannot find such an alternating path, the current matching is as large as possible. The lemma provides a way to verify optimality and guide algorithms for finding the maximum matching.