Hall's Theorem(marriage theorem) I{1,2,,m,UerS≥IIl S1:S2,...,Sm have a SDR case.2:there is a critical family in S1,S2,...Sm Say|Sm-k+1U…USml=k k<m due to I.H.Sm-+1,...,Sm have a SDR X=x1,..,x Si'-SX i=1,2,,m-k Ic{1,2,m-,UcIS≥I due to I.H. S1,...,Sm-k have a SDR Y={y1,...,Umk} X and Y form a SDR for S1,S2,...Sm S1, S2,...,Sm have a SDR Hall’s Theorem (marriage theorem) ⇥I ￾ {1, 2,...,m}, ￾ ￾ ⇥ i￾I Si ￾ ￾ ￾ |I|. case.2: there is a critical family in S1, S2, ..., Sm say k < m due to I.H. |Sm￾k+1 ⇥ ··· ⇥ Sm| = k ⇤I ⇥ {1, 2,...,m ￾ k}, ￾ |I| ￾ ￾ ⇥ i⇥I S￾ i ￾ ￾ due to I.H. X and Y form a SDR for S1, S2, ..., Sm Sm-k+1,..., Sm have a SDR X={x1, ..., xk} Si ’ = Si\X i = 1, 2, ..., m-k S⇥ 1,...,S⇥ m￾k have a SDR Y = {y1,...,ym￾k}