# Graph Theory: Systems of Distinct Representatives

In a collection {$S_1, S_2, ... S_n$} of $n\geq 2$ nonempty sets, no two sets have the same number of elements. Show that this collection has a system of distinct representatives

(a) by using Hall's theorem: A collection {$S_1, S_2, ... S_n$} of $n$ nonempty finite sets has a system of distinct representatives if and only if, for each integer $k$ with $1\leq k\leq n$, the union of any $k$ of these sets contains at least $k$ elements.

(b) without using Hall's theorem.

It seems that I should begin by letting $|S_1|<|S_2|<\cdots<|S_n|$ and showing that, for any union of these sets, I will always get at least $k$ elements. It seems clear to me that the result is true, but I don't know how to prove this exactly.

• Try using the pigeonhole principle. – Gregory J. Puleo Nov 12 '15 at 2:26

HINT: For (a), show that $|S_k|\ge k$ for $k=1,\ldots,n$, and note that if $F\subseteq\{1,\ldots,n\}$, then
$$\left|\bigcup_{k\in F}S_k\right|\ge|S_{\max F}|\;.$$
For (b), suppose not, and let $F\subseteq\{1,\ldots,n\}$ be minimal such that $\{S_k:k\in F\}$ has no SDR. Let $m=\max F$. Let $T$ be an SDR for $\{S_k:k\in F\setminus\{m\}\}$. How must $S_m$ be related to $T$? Is this actually possible?