# Show that a finite regular bipartite graph has a perfect matching

Some preliminaries:

A matching in a bipartite graph with vertex set $X \cup Y$ is a subset $E_1$ of the edge set such that no vertex is incident with more than one edge in $E_1$

A complete matching in a bipartite graph is a matching such that every vertex in $X$ is incident with an edge in $E_1$.

A perfect matching in a graph $G$ (not necessarily bipartite) is a matching such that each vertex of $G$ is incident with one edge of the matching.

Theorem: A necessary and suﬃcient condition for there to be a complete matching from $X$ to $Y$ in $G$ is that $|Γ(A)|≥|A|$ for every $A ⊆ X$. Here $\Gamma(A)$ is used to denote the set of all neighbors of vertices in $A$.

Here's my proof. Can someone please verify it or improve it? I feel that it is a bit hand-waving and lacks much-needed rigor.

Show that a finite regular bipartite graph has a perfect matching

Let $X$ and $Y$ be the (disjoint) vertex sets of the bipartite graph. Let $A \subseteq X$. Then, there are $d|A|$ edges incident with a vertex in $A$. But then, $|\Gamma(A)| \geq |A|$. If that were not the case, then there would exist a vertex $v \in \Gamma(A)$ with $\operatorname{deg}(v) > d$.

So, there exists a complete matching between the vertex sets $X$ and $Y$ of the bipartite graph. Note that this matching is perfect, since $|X| = |Y|$.

• Looks pretty good. May want a few more details if this were something to be graded. For example say a word on why $|X|=|Y|$ (simple edge counting will do). – John Machacek Jul 4 '14 at 10:37

## 1 Answer

The proof is fine. Some feedback:

• It's not true if we allow the possibility of no edges.

• Do you also need to prove $|X|=|Y|$? It follows from the regularity condition. (There are exactly $d|X|$ edges going out of $X$ and so exactly $d|X|$ edges going in $Y$. And so...) I wouldn't leave it hanging like that.

• You should highlight where the theorem is used. "Hence, Theorem 1 implies...".

• I'd rephrase "Then, there are $d|A|$ edges incident with a vertex in $A$." to say "Then, there are $d|A|$ edges incident with the vertices in $A$." (Or simply "there are exactly $d|A|$ edges coming out of $A$".)

• This structure bothers me: "But then, $|\Gamma(A)| \geq |A|$. If that were not the case, then there would exist a vertex $v \in \Gamma(A)$ with $\mathrm{deg}(v)>d$." Specifically, it ends a sentence whose conclusion relies on the next sentence.

I suggest using "..., othewise ..." or brackets. Or rephrasing to "If $|\Gamma(A)|<|A|$, then some vertex in $\Gamma(A)$ has degree $>d$, giving a contradiction. Hence, ...".

• Thank you so much! That was really helpful. – user154185 Jul 4 '14 at 11:21