This is also known as the Marriage Theorem.

Hall’s Theorem

Given a Bipartite Graph $G=(L,R)$, there is a matching that matches all $L$ unless there exists $S\subset L$ such that $|S|>|N(S)|$.

We extend the definition of a neighborhood of vertices to some set $S$, such that

$$N(S)=\{v\in R\mid v\in N(s),s\in S\}$$

Proof:

Start with a maximum matching. If it matches everything on $L$, we are done. Otherwise, there is some unmatched vertex $v\in L$. If $N(v)=\varnothing$, then we are done. Suppose not, then every $w\in N(v)$ must have been matched already. Let $(w,v_1)$ be that matching.

graph LR;
	v((v)) o--o w((w));
	w o--o v1((v1));
	v1 o--o w1((w1));

Consider $N(v_1)$. If there is some $w_1\in N(v_1)$ that has not been matched, we can match $(v_1,w_1)$, freeing $(w,v_1)$, allowing us to match $(v,w)$. On the other hand, $w_1$ may have already been matched. We can repeat this for some $v_2\in N(w_1)$.

This creates an augmenting path, where

$$v=v_0,w_0,v_1,w_1,v_2,w_2,\dots ,v_k,w_k$$

where the edges are $(v_i,w_i)$ and $(w_i,v_{i+1})$ are in the matching, and vertices $v_0,w_k$ are unmatched. The picture here is that

graph LR;
	v0((v0)) -.- w0((w0));
	v1((v1)) o--o w0;
	v1 -.-w1((w1));
	v2((v2)) o--o w1((w1));
	v2 -..-|and so on| wk1;
	vk((vk)) o--o wk1(("w(k-1)"))
	vk((vk)) -.- wk((wk));

Lemma: If the matching has an augmenting path, then it is not maximum.

The proof of this is that we can replace these edges $(w_i,v_{i+1})$ by a bunch of edges $(v_w,w_i)$ which are represented by the dotted lines. In particular, we will now have $k+1$ edges, which is a larger matching set and is a contradiction.

Back to the proof, we know that $v$ must have no augmenting path. Otherwise, we have a contradiction from the lemma.

So, consider

graph LR;
	v((v)) o-.-o Nv[["N(v)"]];
	v o-.-o Nv;
	v o-.-o Nv;
	v o-.-o Nv;
	v o-.-o Nv;
	v o-.-o Nv;
	Nv o--o NNv[["N(N(v))"]];
	Nv o--o NNv;
	Nv o--o NNv;
	Nv o--o NNv;
	Nv o--o NNv;
	Nv o--o NNv;
	NNv o-.-o NNNv[["NNN(v)"]];
	NNv o-.-o NNNv;
	NNv o-.-o NNNv;
	NNv o-.-o NNNv;
	NNv o-.-o NNNv;
	NNv o-.-o NNNv;

and so on. Every one of these vertices must be matched to ensure no augmenting path is possible. Consider every $w\in R$ that are candidates for some augmenting path (all vertices in odd $i$ for $N^i(v)$. All such $w$ are matched. Indeed, let $T$ be the set of such vertices. Let

$$S=\{v\}\cup \{\text{vertices matched to }T\}$$

Firstly, $|S|=|T|+1$ because the vertices in $S$ are vertices matched to $T$, and $v$. Secondly, $N(S)=T$. In particular, we will have found $|S|>|N(S)|$, which means there is no matching, a contradiction.

Proposition (Regular Bipartite Has Perfect Matching)

Every non-empty regular bipartite graph has a perfect matching. That is, there is a matching that matches all vertices.

Proof:

Let the graph be $d-$regular. We apply the Bipartite Handshake Lemma.

$$\begin{array}{rl}\sum _{v\in L}\mathrm{deg}(v)& =\sum _{v\in R}\mathrm{deg}(v)\\ d|L|& =d|R|\\ |L|& =|R|\end{array}$$

Now, it is sufficient to show that for any subset $S\subseteq L$, $|S|\le |N(S)|$ holds, and that by Hall’s Theorem, there is a matching. Let $S$ be some subset, and let $H$ be the [[Graph#Definition (Induced Subgraph)]|induced subgraph]] on $S\cup N(S)$. In $H$, every vertex in $S$ has degree $d$. For $w\in N(S)$, then ${\mathrm{deg}}_H(w)\le d$. By the Bipartite Handshake Lemma,

$$\begin{array}{rl}\sum _{v\in S}{\mathrm{deg}}_H(v)& =\sum _{v\in N(S)}{\mathrm{deg}}_H(v)\\ d|S|& \le d|N(S)|\\ |S|& \le N(S)\end{array}$$

which indicates there is a matching. And as $|L|=|R|$, there must be a perfect matching.

Lemma (Matching Max Degree Left Vertices)

There exists a matching $M$ that matches all of the maximum degree left-vertices.

Proof:

Let $M\subseteq L$ where $v\in M$ has ${\mathrm{deg}}_G(s)=\Delta (G)$. We can consider $G^{\prime }=M\cup N(M)$. By Hall’s Theorem, there is a matching for the LHS vertices, unless $\exists S$ where $|S|>|N(S)|$.

Consider $G^{\prime \prime }$ of just $S\cup N(S)$. By Bipartite Handshake Lemma,

$$\begin{array}{rl}k|S|=\sum _{v\in S}{\mathrm{deg}}_{G^{\prime \prime }}(v)& =\sum _{v\in N(S)}{\mathrm{deg}}_{G^{\prime \prime }}(v)\le k|N(S)|\\ |S|\le |N(S)|& \end{array}$$

but this is a contradiction.