Upper bounds on the number of perfect matchings and directed 2-factors in graphs with given number of vertices and edges

摘要

We give an upper bound on the number of perfect matchings in simple graphswith a given number of vertices and edges. We apply this result to give anupper bound on the number of 2-factors in a directed complete bipartitebalanced graph on 2n vertices. The upper bound is sharp for n even. For n oddwe state a conjecture on a sharp upper bound.