Number of distinct perfect matching in a d-regular graph.

67 Views Asked by At

I have a claim that every d-regular bipartite graph has at least d! distinct perfect matchings. Is this claim is true? if yes then can somebody tell me the proof? Actually there is a problem that ask to show that any r X n latin rectangle can be extended to a n X n latin square and there are at least (n-r)! ways to do it. Now this problem can be easily reduced to a (n-r) regular bipartite graph(V=X U Y) where X = [n] and Y = set of Bj where Bj is the set of number that are not present in column j. You can also see this math.toronto.edu/gscott/MAT332notes_latinsquares.pdf