Hall’s theorem revisited

Abstract:

Let $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}$ can be extended to a set of distinct representatives of $\{A_{i}\}_{i=1}^{n}$ in more than $\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.