Hall's Theorem(marriage theorem) IC{1,2,.,mh,lUeS≥I. >S1,S2,...,Sm have a SDR case.I:there is no critical family in S1,S2,...,Sm VI C {1,2,...,m}that I m,Uier Si take an arbitrary xESm as representative of Si remove Sm and x Si'=SAfx}i=1,2,...m-1 I{1,2,,m-1},UcS≥lI川 due to I.H.S1...,Sm-1 have a SDR {1,....m-1 1,...,m-1 and x form a SDR for S1,S2,...Sm case.1: there is no critical family in S1, S2, ..., Sm take an arbitrary x∈Sm as representative of Sm remove Sm and x Si ’ = Si\{x} i = 1, 2, ..., m-1 ⌅I ⇥ {1, 2,...,m ￾ 1}, ￾ ￾ ⇥ i⇥I S￾ i ￾ ￾ ⇤ |I| ⇥I ￾ {1, 2,...,m} that |I| < m, ￾ ￾ ⇥ i￾I Si ￾ ￾ > |I| due to I.H. S1, S2,...,Sm have a SDR Hall’s Theorem (marriage theorem) ⇥I ￾ {1, 2,...,m}, ￾ ￾ ⇥ i￾I Si ￾ ￾ ￾ |I|. S⇥ 1,...,S⇥ m￾1 have a SDR {x1,...,xm￾1} x1,...,xm￾1 and x form a SDR for S1, S2, ..., Sm