A -factor of a graph is a -regular spanning subgraph, that is, a subgraph with .
Let be a bipartite graph with vertex classes and . A matching in is a set of independent edges.
If then a matching is a 1-factor.
Let be a bipartite graph with vertex classes and . Then has a matching iff for every .
Join a new vertex to all elements of and a new vertex to all elements of to form .
Suppose is a set of vertices separating from . Then . Now . So . By Hall's condition . So . By the choice of , .
Using Menger's theorem there are independent paths, giving a matching in .
By induction on .
The case is trivial.
Suppose that for every with we have . Then take any . satisfies Hall's condition. By the induction hypothesis has a matching, so has a matching.
Otherwise there exists a critical set , with . Let and .
clearly satisfies Hall's condition. Let . Now .
So by induction hypothesis there is a matching on and , giving a matching in .
Let be an integer. If for all then there is a matching of all but elements of .
Let be an integer. If for all , then we can match each to elemens of , the different element sets being disjoint.
John Fremlin 2010-02-17