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)