0
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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). $\endgroup$ – John Machacek Jul 4 '14 at 10:37
2
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.