Hall's Theorem(marriage theorem) ∀I{1,2,,m,Uc1S≥lI1. S1:S2:...,Sm have a SDR critical family:S1,S2,...,k k<m k . =k i=1 Induction on m: m =1,trivial case.I:there is no critical family in S1,S2,...,Sm case.2:there is a critical family in S1,S2,...,SmS1, S2,...,Sm have a SDR Hall’s Theorem (marriage theorem) ⇥I ￾ {1, 2,...,m}, ￾ ￾ ⇥ i￾I Si ￾ ￾ ￾ |I|. Induction on m : m =1, trivial case.1: there is no critical family in S1, S2, ..., Sm case.2: there is a critical family in S1, S2, ..., Sm critical family: S1, S2,...,Sk ￾ ￾ ￾ ￾ ￾ ⇥ k i=1 Si ￾ ￾ ￾ ￾ ￾ = k k < m