The maximum number of perfect matchings in graphs with a given degree sequence

Abstract

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

2 pages

References in corpus (1)

• An upper bound for the number of perfect matchings in graphs