# An application of Hall's marriage theorem.

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.

• Take any subset of ranks, call it $A$. Because there are 4 cards for each rank, it has at least $4|A|$ connections, thus it has to connect to at least $4|A|/4=|A|$ card piles. Hence $|N(A)| \geq |A|$. Aug 5 '16 at 16:27
• I do not agree that A has at least 4 |A| connections. It could have as few as |A|. Right? Aug 5 '16 at 16:46
• By connections I mean edges in a multigraph. That means $A$ has at least $|A|$ neighbors in the multigraph, but then if you merge multiple repated edges into a single one to obtain a normal graph, the number of neighbors doesn't change. Aug 6 '16 at 8:00
• OK! Thank you. I agree. Aug 6 '16 at 12:09

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.
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.