An application of Hall's marriage theorem.

Question

I am reading the Wikipedia article entitled Hall's marriage theorem. It states we can use the theorem to prove the following:

"Take a standard deck of cards, and deal them out into 13 piles of 4 cards each. Then, using the marriage theorem, we can show that it is always possible to select exactly 1 card from each pile, such that the 13 selected cards contain exactly one card of each rank (Ace, 2, 3, ..., Queen, King)."

The article doesn't say HOW Hall's theorem can be used to prove this.

I think we could create a bipartite graph with one partite set consisting of each of the 13 ranks and the other partite set consisting of the 13 piles. An edge joins a rank to a pile if that rank is in the pile. Each rank would be joined to at least one pile and at most 4 piles. This is as far as I have gotten.

Answer 1

You are exactly right, create a bipartite graph, with $13$ vertices in each side, on one side you have the $13$ piles and on the other the $13$ ranks. Connect a pile with a rank if and only if the pile contains the rank.

If we can find a perfect matching we would be done, because for each pile you select one card with the rank to which the pile is connected, and no two selected cards will have the same rank.

We must only prove that this graph has a perfect matching, we use Hall's theorem.

Select any subset of ranks, say they are $k$, we must prove that there are at least $k$ piles that contain at least one card from one of the ranks. Suppose not, then we can find $k-1$ piles that contain all of the cards from the $k$ ranks, impossible, since there are $4k$ cards from the selected ranks, and those piles would have $4(k-1)$ cards.