[Math] Show that a finite regular bipartite graph has a perfect matching

graph theoryproof-verification

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 sufficient 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|$.

Best 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, ...".

Related Question