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·

up vote 7 down vote accepted

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.

  • Sorry if I misread, but doesn't the vertex $u_n$ have degree 1? – monkeymaths Feb 2 '17 at 9:36
  • That's beautifully simple. The problem with choosing greedily in the original setting is that after your first choice both $n$ and the minimum degree might have dropped by $1$. But if you first replace the minimum degree condition by (Philip) Hall's condition, then restrict to a minimal set of vertices where Hall's condition is tight (which must have size at least $r$), it now plays nicely with induction. – Ben Barber Feb 2 '17 at 10:23
  • @monkeymaths Yes, which is related to (Marshall) Hall's result only needing the existence of a perfect matching and a one-sided minimum degree. It's not a sharp answer to the question as I happened to phrase it, but it still says that there are lots of perfect matchings. – Ben Barber Feb 2 '17 at 10:26

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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