All Questions
1 question
6
votes
2
answers
7k
views
How many perfect matchings in a regular bipartite graph?
We have a $d$-regular bipartite graph $G = (X,Y,E)$ with $|X| = |Y| = n$ and $|E| = nd$.
What is an upper bound on the number of perfect matchings of $G$?
- 61