Department of Computer Science and Technology,Nanjing University Hal定理 (2)存在V的一个真子集A',N(A'川 =A'.记B'=N(A'). 据归纳假设，存在A'到B'的完备匹配. 二部图H=G-A'-B'满足归纳假设条件 否则，存在CsV1-A'.N(C)K|C. ING(CUA)I INH(C)+B'<JCH+IB'=CH+IA'ICUA'L 矛盾. 据归纳假设，存在V1-A'到V2-B'的完备匹配. 合并上述两个匹配得到一个V到V,的完备匹配.得证 June 2016 11June 2016 11 Department of Computer Science and Technology, Nanjing University Hall定理 (2)存在 V1的一个真子集A', |N(A')| =|A' |. 记B'= N(A'). 据归纳假设,存在A'到B' 的完备匹配. 二部图H=G-A'-B' 满足归纳假设条件. A' B' 否则, 存在C V1 -A'. |NH(C)|<|C|. |NG(CA')| |NH(C)|+|B'|<|C|+|B'|=|C|+|A'|= |CA'|. 矛盾. 据归纳假设,存在V1 -A'到V2 -B'的完备匹配. 合并上述两个匹配得到一个V1到V2的完备匹配. 得证