I have only seen Hall's theorem applied on the marriage problem. For the problem below I have to use this theorem I guess. For me it's still difficult to apply this to a problem.
Problem:
Consider $n$ winners from a lottery. Al these winners may choose two prices from a big collection of prices. There is one copy of each price. Every winner select several prices he may want. Give a necessary and sufficient condition such that every winner gets two prices he selected. Proof your claims.
We can start with a set $A$ of winners and a set $B$ of prices. Then $|A| = n$. Assume we have $p$ prices, so $|B| = p$. But how to go further? It must be something with proving there is a link between the elements in $A$ and $B$.
Best Answer
You need to "clone" each of the winners. Now $|A|=2n$. Each winner $W$ has two clones $W_1$ and $W_2$. Now the vertices of the bipartite graph are all the clones on one side, and all the prizes on the other. Each clone has an edge to all the prizes that the winner wants.
A matching covering all the clones will assign each clone exactly one prize, and each prize at most once. Now, give the winner the two prizes matched by his or her clones. On the other hand, if it is possible to award each winner two prizes, then that will give you a matching of this bipartite graph.
Now you are ready to apply Hall's theorem. It states that a desired matching exists exactly when for every subset $C\subseteq A$, there are at least $|C|$ elements of $B$ they are matched to.
In one direction, i.e. proving that a matching exists, we may assume for our problem that without loss that $C$ includes both clones of each winner. Otherwise, we may add the other clone in to $C$, to make $|C|$ larger and the set of prizes they are matched to unchanged. Consequently, condition $(\star)$ below is sufficient to prove that a prize distribution exists.
$(\star)$ for every set of winners $D$, there are at least $2|D|$ prizes that they mutually would like.