ABSTRACT
Consider a bipartite graph G = (U, V,E), where U and V are sets of vertices and E is a set of edges. A matching M of G is a subset of E such that each vertex appears at most once in M . Bipartite matchings are sometimes characterized as the marriage between a man and a woman: U and V represent the sets of men and women, respectively, and the existence of an edge between m ∈ U and w ∈ V implies that m and w are acceptable to each other.
