# Matchings

Definition 5..1 (-factor)

A -factor of a graph is a -regular spanning subgraph, that is, a subgraph with .

Definition 5..2 (Matching)

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.

Theorem 5..3 (Hall's marriage theorem)

Let be a bipartite graph with vertex classes and . Then has a matching iff for every .

Proof. [Using Menger's theorem]

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 .

Proof. [Direct]

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 .

Corollary 5..4 (Defect form of Hall's theorem)

Let be an integer. If for all then there is a matching of all but elements of .

Proof. Add extra vertices to connected to all vertices of . Then by Hall's theorem there is a matching. Remove the additional vertices, to make a matching of all but elements of .

Corollary 5..5 (Polygamous form)

Let be an integer. If for all , then we can match each to elemens of , the different element sets being disjoint.

Proof. Replace each with nodes connected to . Hall's theorem gives a matching.

John Fremlin 2010-02-17