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$.


1 Answer 1


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.

  • 3
    $\begingroup$ 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: emis.ams.org/journals/EJC/Volume_15/PDF/v15i1n13.pdf. 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. $\endgroup$ Apr 17, 2010 at 21:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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