*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