Disjoint matchings of graphs

AbstractIn this paper, we prove a generalization of the familiar marriage theorem. One way of stating the marriage theorem is: Let G be a bipartite graph, with parts S1 and S2. If A ⊂ S1 and F(A) ⊂ S2 is the set of neighbors of points in A, then a matching of G exists if and only if Σx∈S2 min(1, | F−1(x) ∩ A |) ≥ | A | for each A ⊂ S1. Our theorem is that k disjoint matchings of G exist if and only Σx∈S2 min (k, | F−1(x) ∩ A |) ≥ k | A | for each A ⊂ S1