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·

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Sorry if I misread, but doesn't the vertex $u_n$ have degree 1? $\endgroup$
    – monkeymaths
    Commented 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
    Commented 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
    Commented Feb 2, 2017 at 10:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .