Lower bound on counting perfect matchings in bipartite graph

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

• 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. – hardmath Sep 23 '14 at 18:43
• Yes thanks for your remark. This may help me. – lafaillette Sep 23 '14 at 22:12
• Helpful enough that it would worth posting the details as an Answer? – hardmath Sep 23 '14 at 22:15
• 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. – lafaillette Sep 23 '14 at 23:24
• But if a matching saturates (covers?) $V_1$, will it not necessarily be a perfect matching, since $|V_1|=|V_2|$ ? – hardmath Sep 23 '14 at 23:38

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.

• 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$? – lafaillette Sep 24 '14 at 22:09
• @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$. – hardmath Sep 25 '14 at 0:57