Let S be a finite set and let S 1, S 2, …, St be subsets of S, not necessarily distinct. Does there exist a set of distinct representatives (SDR) for S 1, S 2, …, St ? That is, does there exist a subset {a 1, a 2, …, at } of S such that ai ∊ Si , 1 ≦ i ≦ t, and ai ≠ aj if i ≠ j? The following theorem of Hall [2; 6, p. 48] gives the answer.
THEOREM. The subsets S 1, S 2, …, St have an SDR if and only if for each s, 1 ≦ s ≦ t, |S i1 ∪ S i1 ∪ … ∪ Sis | ≧ s for each s-comhination {i 1, i 2, …, is } of the integers 1, 2, …, t.
(Here and below, |A| denotes the number of elements in A.)