3
$\begingroup$

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·

$\endgroup$

1 Answer 1

7
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Sorry if I misread, but doesn't the vertex $u_n$ have degree 1? $\endgroup$ Feb 2, 2017 at 9:36
  • $\begingroup$ 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. $\endgroup$
    – Ben Barber
    Feb 2, 2017 at 10:23
  • $\begingroup$ @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. $\endgroup$
    – Ben Barber
    Feb 2, 2017 at 10:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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