MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

What is the maximal number of perfect matchings a graph $G(V,E)$ can have if $|V|$ and $|E|$ are fixed? I am particularly interested in a case when $|E| = c|V|^2$.

share|cite|improve this question
up vote 11 down vote accepted

I think this is exactly the main result of this recent paper we just published in Discrete Mathematics. Just in case the link doesn't work: this is "Graphs with the maximum or minimum number of 1-factors" by D. Grossa, N. Kahl and J.T. Saccoman. I have read only the abstract. Let me know if this is what you were looking for.

share|cite|improve this answer
Thank you, this paper really gives the answer. In fact, it seems that the main result was obtained by Alon and Friedland in this paper: There they show that graphs which are union of complete bipartite graphs have the maximum number of perfect matchings among all graphs with the same degree sequence. – Grigory Yaroslavtsev Apr 17 '10 at 21:42

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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