Skip to main content
MathOverflow

Return to Question

corrected title, improved grammar
Source Link
edit approved Oct 9, 2014 at 8:32
bof
edit approved Oct 9, 2014 at 8:32
bof
  • 13.4k
  • 2
  • 43
  • 66

Minimum number of perfect matchings in a regular bipartite matchinggraph

Is there a lower bound on the number of perfect matchings in a $k$-regular bipartite graph?

One can use Hall'sHall's marriage theorem and induction on $k$ to derive the lower bound of $k$. I can't come up with an example where this bound is actually tight. Is there a better lower bound tothan this?

Minimum number of perfect matchings in a regular bipartite matching

Is there a lower bound on number of perfect matchings in a $k$-regular bipartite graph?

One can use Hall's marriage theorem and induction on $k$ to derive the lower bound of $k$. I can't come up with an example where this bound is actually tight. Is there a better lower bound to this?

Minimum number of perfect matchings in a regular bipartite graph

Is there a lower bound on the number of perfect matchings in a $k$-regular bipartite graph?

One can use Hall's marriage theorem and induction on $k$ to derive the lower bound of $k$. I can't come up with an example where this bound is actually tight. Is there a better lower bound than this?

Source Link
Untitled
Untitled
  • 217
  • 1
  • 7

Minimum number of perfect matchings in a regular bipartite matching

Is there a lower bound on number of perfect matchings in a $k$-regular bipartite graph?

One can use Hall's marriage theorem and induction on $k$ to derive the lower bound of $k$. I can't come up with an example where this bound is actually tight. Is there a better lower bound to this?