The Maximum Number of Perfect Matchings in Graphs with a Given Degree Sequence

Noga Alon, Shmuel Friedland

Abstract


We show that the number of perfect matchings in a simple graph $G$ with an even number of vertices and degree sequence $d_1,d_2, \ldots ,d_n$ is at most $ \prod_{i=1}^n (d_i!)^{{1\over 2d_i}}$. This bound is sharp if and only if $G$ is a union of complete balanced bipartite graphs.


Full Text: PDF