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.

Published
2008-04-24
Article Number
N13