Question

We have a poker deck of 52 cards. Abby randomly shuffles the card, and divides it into 13 piles of 4 cards each. Use Hall marriage theorem to show that it is possible to pick a card from each pile, so that you get all 13 numbers from A to K.

Answer 1

Consider the bipartite graph where LHS corresponds to the 13 piles and RHS corresponds to the 13 ranks.

Put an edge from a pile to the rank if the pile contain at least one card of the rank

At first this appears to be a special case for perfect matching with k=4, but now we have a problem of multiple edges, spike might be all kings

For any set X and consider N(X) , the number of edges coming out of X is exactly K|X|. But each vertex in N(X) can only absorb K many of them so N(X)|X|

G is a bipartite graph with all degree equal to K then G has a perfect matching

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−1piles 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.

In other way - Consider a bipartite graph G[X, Y ], where X is the set of 14 piles and Y is the set of 14 possible ranks, and each pile is connected by an edge with the ranks that appear in it. Clearly, for any k piles, there are at least k ranks appearing in them. Thus, the marriage condition is satisfied, and therefore we have a perfect matching.