Extremal Graphs With a Given Number of Perfect Matchings

Let f ( n , p ) denote the maximum number of edges in a graph having n vertices and exactly p perfect matchings. For fixed p , Dudek and Schmitt showed that f ( n , p ) = n 2 / 4 + c pfor some constant c p when n is at least some constant n p . For p ≤ 6 , they also determined c p and n p . For fixed p , we show that the extremal graphs for all n are determined by those with O ( p ) vertices. As a corollary, a computer search determines c p and n p for p ≤ 10 . We also present lower bounds on f ( n , p ) proving thatc p > 0 for p ≥ 2 (as conjectured by Dudek and Schmitt), and we conjecture an upper bound on f ( n , p ) . Our structural results are based on Lovász's Cathedral Theorem.