Take the tour ×  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|improve this question add comment  1 Answer  up vote 10
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|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: 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. –  Grigory
Yaroslavtsev Apr 17 '10 at 21:42 add co