[Math] Number of perfect matchings in bipartite graph with given minimum degree

co.combinatoricsgraph theorymatching-theoryperfect-matchings

Let $G$ be a spanning subgraph of $K_{n,n}$ with minimum degree $\delta(G) \geq n/2$. It's easy to show using Hall's theorem that $G$ has a perfect matching, and the example of two disjoint copies of $K_{\lfloor n/2 \rfloor + 1, \lceil n/2 \rceil – 1}$ side by side shows that $n/2$ is sharp. This extremal example "almost" has lots of perfect matchings—it has lots of matchings covering almost all of the vertices.

If $\delta(G) \geq n/2$, how many perfect matchings must $G$ contain?

For $k$-regular bipartite graphs the answer to the corresponding question is due to Schrijver.

A closely related question did not focus on the range of degrees where perfect matchings are guaranteed·

Best Answer

It's a theorem of Marshall Hall that in a bipartite graph of minimum degree $r$, where there exists a perfect matching, there will be at least $r!$ perfect matchings. In your case the conditional disappears and you get a lower bound of $\lceil\frac{n}{2}\rceil!$ perfect matchings.

This lower bound is tight, and it's achieved by the graph on vertices $u_1,v_1,\dots,u_n,v_n$, where there is an edge betweenn $u_i$ and $v_j$ for all $i,j\le \lceil\frac{n}{2}\rceil$, and an edge for all $i\le j$. A perfect matching in this graph must contain edges $u_iv_i$ for all $i > \lceil \frac{n}{2}\rceil$, therefore it contains exactly $\lceil\frac{n}{2}\rceil!$ perfect matchings.

Related Question