I have a math problem that states the following:

Problem: Show that a k-regular bipartite graph G = (S+T, E) contains at least k! matchings with |S| = |T| number of edges.

Solution: So far I have proved that |S| = |T| for G by using the property of a regular graph (that the sum of vertex degrees v, u in S, T are the same), and that G always contains a matching M with |M| = |S| = |T|. I have gotten a hint to perform induction on n = |S| = |T| to solve the problem, but I'm not very confident with proofs by induction.

Can anyone point me in the right direction here?


I think a good start would be to use König's line coloring theorem (the one about edge chromatic numbers, don't confuse with the other König's theorem about min vertex cover/max matching)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.