An upper bound for the number of perfect matchings in graphs

Abstract

We give an upper bound on the number of perfect matchings in an undirected simple graph $G$ with an even number of vertices, in terms of the degrees of all the vertices in $G$. This bound is sharp if $G$ is a union of complete bipartite graphs. This bound is a generalization of the upper bound on the number of perfect matchings in bipartite graphs on $n+n$ vertices given by the Bregman-Minc inequality for the permanents of $(0,1)$ matrices.

6 pages

Cited by in corpus (3)

• Three tutorial lectures on entropy and counting
• The maximum number of perfect matchings in graphs with a given degree sequence
• Asymptotics of the Upper Matching Conjecture