Theorem 8.3 Let G be a bipartite graph with partite sets U and W such that r=Us W.Then G contains a matching of cardinality r if and only if G satisfies Hall's condition. ·Case2:存在一个U的真子集X,IN(X)川=X ·X和N()之间满足Hal条件，经归纳假设，存在W完满匹配 ·构造H子图：U-X和W-N(X),尝试证明H中有最大匹配 ·任取U-X中的子集s,H图中s'=NS)n(W-N() W ·1S1<=?1S1吗？ ·IN(XUsl>=|XUs|(Hall条件) N() Si .IN(X)I+S'I=IN(XUS)I>=I XUS I=IXI+SI IN(X)I=|X刈 ·IsI>=lsl ·H中有最大匹配M” U ·构造G中匹配M'+• Case2：存在一个U的真子集X，|N(X)|=|X| • X和N(X)之间满足Hall条件，经归纳假设，存在M’完满匹配 • 构造H子图：U-X和W-N(X)，尝试证明H中有最大匹配 • 任取U-X中的子集S，H图中S’=N(S)∩(W-N(X)) • |S|<=?|S’|吗？ • |N(XꓴS)|>=| XꓴS | （Hall条件） • |N(X)|+|S’|=|N(X ꓴ S)|>=| XꓴS |=|X|+|S| • |N(X)|=|X| • |S’|>=|S| • H中有最大匹配M’’ • 构造G中匹配M’+M’’ U W X N(X) S S’