Factorially many maximum matchings close to the Erdős-Gallai bound

Abstract

A classical result of Erdős and Gallai determines the maximum size $m(n,\nu )$ of a graph $G$ of order $n$ and matching number $\nu n$. We show that $G$ has factorially many maximum matchings provided that its size is sufficiently close to $m(n,\nu )$.