Donovan Young on Nostr: Perfect matchings aren't always possible. For example if we have a bi-partite graph ...

Perfect matchings aren't always possible. For example if we have a bi-partite graph with \(k=2\) sets of unequal size, we won't be able to match-up each vertex without leaving some unmatched.

If the two sets are of the same size \(k_1\), then there are \(k_1!\) perfect matchings. We can understand this count as follows:

Imagine that the \(k_1\) edges are coloured with \(k_1\) different colours, then there are \(k_1!\) ways to attach the \(k_1\) vertices in the first set to (one side of) the \(k_1\) edges. There are also \(k_1!\) ways to attach the \(k_1\) vertices in the second set to (the other sides of) the \(k_1\) edges. But then we should divide by the \(k_1!\) ways of colouring the edges as they are, in fact, indistinguishable. This gives:

\(\frac{k_1!k_1!}{k_1!} = k_1!\) .

(If this counting seems a little heavy-handed to you, I am using it because it generalises nicely to higher \(k\).)