# 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). Jul 4, 2014 at 10:37

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. Jul 4, 2014 at 11:21