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