Theorem 5.27(Hall's Theorem) Let G(vi; V2) be a bipartite graph with visv2l Then G has a complete matching saturating every vertex of Vi iff SEN(S) for every subset scv Example: Let g be a k-regular bipartite graph. Then there exists a perfect matching of g, where k0 regular For acv,erele incident a vertex ofa, eisele incident a vertex ofN(a) For ve∈E1,eeE2 Thus e1∈E2. Therefore e1E2 Because KA|=E1≤E2=kN(A川,N(A)A By Halls theorem, g has a complete matching M from VI to V2. Because vi=val, Thus M is a perfect matching▪ Theorem 5.27 (Hall's Theorem) Let G(V1 ; V2 ) be a bipartite graph with |V1 |≤|V2 |. Then G has a complete matching saturating every vertex of V1 iff |S|≤|N(S)| for every subset SV1 ▪ Example: Let G be a k-regular bipartite graph. Then there exists a perfect matching of G, where k>0. ▪ k-regular ▪ For AV1 ,E1={e|e incident a vertex of A}, E2={e|e incident a vertex of N(A)} ▪ For eE1 , eE2 . Thus E1E2 . Therefore |E1 |≤|E2 |. ▪ Because k|A|=|E1 |≤|E2 |=k|N(A)|, |N(A)|≥|A|. ▪ By Hall’s theorem, G has a complete matching M from V1 to V2 . ▪ Because |V1 |=|V2 |, Thus M is a perfect matching