Hall's Theorem

Let Graph be bipartite. There exists a Matching from to if and only if for all ,

Proof

If there is a matching, we can find an injection from to

Now suppose for all We go by induction on

Case 1

Suppose there is some such that Then satisfies the criterion so there is a matching on Also set and Write:

Thus

Case 2

For all we have Pick connected vertices Let Let Then:

So So apply induction hypothesis.

Corollary

If is -regular bipartite, then there exists a matching.

Proof

Compute the number of edges in two ways, as all the edges from and all the edges from