Hall’s theorem revisited
Zhi‐Wei Sun · Proceedings of the American Mathematical Society · 2001
Let A 1 , ⋯ , A n ( n > 1 ) A_{1},\cdots ,A_{n}\ (n>1) be sets. By a simple graph-theoretic argument we show that any set of distinct representatives of { A i } i = 1 n − 1 \{A_{i}\}_{i=1}^{n-1} can be extended to a set of distinct representatives of { A i } i = 1 n \{A_{i}\}_{i=1}^{n} in more than min n ∈ I ⊆ { 1 , ⋯ , n } ( | ⋃ i ∈ I A i | − | I | ) \min _{n\in I\subseteq \{1,\cdots ,n\}} (|\bigcup _{i\in I}A_{i}|-|I|) ways. This yields a natural induction proof of the well-known theorem of P. Hall.