# Maximum number of perfect matchings in a graph

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

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.

-
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