1
$\begingroup$

Let $G=(V_1 \cup V_2,E)$ be a finite bipartite graph. If every vertex in $V_1$ has degree at least $r\le|V_1|$ and $G$ has a perfect matching, we want to show there are at least $r!$ complete matchings from $V_1$.

I wanted to use the number of injections between two sets of $r$ elements but I cannot find out such sets...

By the way since $G$ has a perfect matching, we have $|V_1|=|V_2|$. Plus we can use Hall's theorem which claims that $\forall S \subset V_1,\,|N_G(S)|\geq |S| $, it is also right for $V_2$.

$\endgroup$
  • $\begingroup$ In order for $G$ to have a perfect matching, $|V_1|=|V_2|$. Every perfect matching defines an injection (and surjection) from $V_1$ to $V_2$, but the converse is not true. The number of perfect matchings is easily expressed as a permanent, but this unfortunately does not make it easy to compute. $\endgroup$ – hardmath Sep 23 '14 at 18:43
  • $\begingroup$ Yes thanks for your remark. This may help me. $\endgroup$ – lafaillette Sep 23 '14 at 22:12
  • $\begingroup$ Helpful enough that it would worth posting the details as an Answer? $\endgroup$ – hardmath Sep 23 '14 at 22:15
  • $\begingroup$ Well I'm thankful for reminding me $|V_1|=|V_2|$ but your comment, however useful, does not answer the problem. I have to count matchings saturating $V_1$, not perfect matchings. $\endgroup$ – lafaillette Sep 23 '14 at 23:24
  • $\begingroup$ But if a matching saturates (covers?) $V_1$, will it not necessarily be a perfect matching, since $|V_1|=|V_2|$ ? $\endgroup$ – hardmath Sep 23 '14 at 23:38
1
$\begingroup$

Let $G$ be a finite bipartite graph with bipartition $V_1 \cup V_2$. If $G$ has at least one perfect matching, and every vertex in $V_1$ has degree at least $r$, we are to prove a lower bound $r!$ on the number of perfect matchings.

A theorem of Phillip Hall (1935) gives the well-known necessary and sufficient "Hall's Condition" for a matching that covers $V_1$, already mentioned in the Question above. For every subset $S \subseteq V_1$, let $N(S) \subseteq V_2$ be the set of nodes adjacent to some node in $S$.

Bipartite graph $G$ has a matching that covers finite $V_1$ if and only if for every subset $S \subseteq V_1$, $|N(S)| \ge |S|$.

In 1948 Marshall Hall Jr. (no relation) published a refinement of Philip Hall's result which gives the desired lower bound on the number of different matchings that cover $V_1$:

If $r = \text{min}_{v \in V_1} \text{deg}(v)$, then there are at least $\prod_{i=1}^{\text{min}\{r,|V_1|\}} (r+1-i)$ matchings covering $V_1$.

For the sake of completeness we will give a proof of this, but since we've stated matters in greater generality than required for the Question, let's begin by verifying that in our specific case the lower bound amounts to $r!$. Since a perfect matching exists, $|V_1| = |V_2|$, and since $r \le |V_2|$, the upper limit of the product is simply $r=\text{min}\{r,|V_1|\}$, and:

$$\prod_{i=1}^r (r+1-i) = r\cdot (r-1)\ldots \cdot 1 = r! $$

The following proof is closely adapted from Thm. 2.1.5 of D.B. West's The Art of Combinatorics - Volume I. Extremal Graph Theory, Chapter 2: Matching and Independence.

The necessity of Hall's Condition is easy, since any matching that covers $V_1$ will cover any $S \subseteq V_1$, implying that $|N(S)| \ge |S|$. The sufficiency will now be shown by proving the stated lower bound by induction on $m = |V_1|$.

For the basis step $m=1$ we have $r$ matchings, since that is the degree of the one vertex in $V_1$.

Now let $m gt 1$. Consider two cases:

Case 1: Suppose a strict inequality throughout Hall's Condition, that is:

$$ |N(S)| \gt |S| \; \text{ for every nonempty proper subset } \; S \subset V_1 $$

For fixed node $u \in V_1$, choose any adjacent node $v \in V_2$. This can be chosen in at least $r$ ways. Whichever choice is made, $G - \{u,v\}$ still satisfies Hall's Condition because no subset of $V_1 - {u}$ has lost more than one neighbor, and we have the strict inequality above allowing for that loss. Each node of $V_1 - {u}$ has degree at least $r-1$, so applying the induction hypothesis and multiplying by the factor $r$ just mentioned gives the desired lower bound in this case.

Case 2: On the other hand suppose there exists nonempty proper subset $S \subset V_1$ for which $|N(S)| = |S|$. A matching that covers $V_1$ will necessarily amount to a matching on the restriction $G_1$ of $G$ to $S \cup N(S)$ and another matching on $G_2$ the restriction of $G$ to $G - (S \cup N(S))$. Since $G_1$ contains all the neighbors of $S$, the minimum degree of $S$ nodes in $G_1$ is $r \le |N(S)| = |S|$. The induction hypothesis therefore applies to the number of matchings that cover $S$ in $G_1$ to give at least:

$$ \prod_{i=1}^r (r+1-i) $$

The induction hypothesis also applies to give at least one matching that covers $V_1 - S$ in $G_2$, since if there were a node $u \in (V_1 - S)$ that had neighbors only in $N(S)$, then $S' = S \cup \{u\}$ would be a subset of $V_1$ for which Hall's Condition fails.

It follows that the above product is also a lower bound on the number of matchings that cover $V_1$ in $G$. This completes the second case, and thus the proof by induction.

$\endgroup$
  • $\begingroup$ Thanks a lot that's brilliant. Still I'm not sure to understand how you can apply the induction hypothesis to $V_1 - S$ in $G_2$. I think I understand the part with $\forall u\in(V_1 -S),\, d_{G_2}(u) \geq 1 \leq |V_1-S|$, that's right no? But how do you prove the existence of a perfect matching in $G_2$? More precisely I can't understand the statement: " A matching that covers $V_1$ will necessarily amount to a matching on $G_2$". What if there were some edge between $(V_1 - S)$ and $N(S)$ used by the initial perfect matching of $G_1$? $\endgroup$ – lafaillette Sep 24 '14 at 22:09
  • $\begingroup$ @QuentinPergeline: You've parsed some of the details in Case 2, but you seem concerned about something that does not happen. You abbreviated my quoted statement. Big picture is we piece together $r!$ matchings over $S$ to $N(S)$ with just a single matching from $(V_1 - S)$ to $V_2 - N(S)$. There are no edges between $(V_1 - S)$ and $N(S)$ used by the $r!$ matchings of $G_1$. $\endgroup$ – hardmath Sep 25 '14 at 0:57

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.