ON THE NUMBER OF PERFECT MATCHINGS IN A BIPARTITE GRAPH.

In this paper we show that, with 11 exceptions, any matching covered bipartite graph on n vertices, with minimum degree greater than two, has at least 2n - 4 perfect matchings. Using this bound, which is the best possible, and McCuaig's theorem [W. McCuaig, J. Graph Theory, 38 (2001), pp. 124-169] on brace generation, we show that any brace on n vertices has at least (n-2)²/8 perfect matchings. A bi-wheel on n vertices has (n - 2)²/4 perfect matchings. We conjecture that there exists an integer such that every brace on n ≥ N vertices has at least (n-2)²/4 perfect matchings. [ABSTRACT FROM AUTHOR]