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

2008/03/18 by Noga Alon, Shmuel Friedland, Alon, Noga +1
Computer Science · Mathematics · #05A15 #05C70 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #math.CO #msc:05A15 #msc:05C70

paper · pdf · doi:10.48550/arxiv.0803.2578

2 pages

openalex publication_date 2008/03/18 · arxiv created 2008/05/26 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We show that the number of perfect matching in a simple graph G with an even number of vertices and degree sequence d₁,d₂, ..., d_n is at most ∏_i=1ⁿ (d_i !)^(1)/(2d_i). This bound is sharp if and only if G is a union of complete balanced bipartite graphs.

Related

• An upper bound for the number of perfect matchings in graphs
• The maximum number of perfect matchings of semi-regular graphs
• Upper bounds on the number of perfect matchings and directed 2-factors in graphs with given number of vertices and edges
• Degree sequences realizing labelled perfect matchings
• Sharp lower bounds for the number of maximum matchings in bipartite multigraphs