Q:

How many  Perfect Matchings in a regular bipartite Graph

Hi Guys,
We have a d-regular bipartite Graph $G = (X,Y,E)$ with $|X| = |Y| = n$ and $|E| = nd$. i want to know a Upper Bound of the number of Matching
Thankx

A:

To elaborate on Tony's answer, for a graph $G$ with an even number of vertices and degree sequence $d_1,\dots,d_n$ the number of matchings in $G$ is at most $\prod_{i=1}^n (d_i!)^{\frac{1}{2d_i}}$, with equality achieved only at graphs which are a disjoint union of complete bipartite graphs. The proof is a consequence of the Bregman inequality for permanents. See "The maximum number of perfect matchings in graphs
with a given degree sequence", by Alon and Friedland
Notice that there is a conjecture that something similar holds for the number of matchings of size $t$ where $t$ is not necessarily half the number of vertices. It is conjectured that this is also maximized at disjoint union of complete bipartite graphs, but is open in general (even when we restrict to only bipartite graphs).

