Department of Computer Science and Technology,Nanjing University Hall定理的推论 ·设二部图G是一个k-正则的(k≥1)，则G有完美匹配. 证明.不妨设G=<A,B,E>,kA=kB,所以A=BL, 下证G有A到B的完备匹配. 对任一S∈A,S与NS)之间总共有kS条边，而与 N(S)相关的边总共有kN(S)条边。 '.kS≤kNS)川 ∴.N(S)川≥ISI 根据Ha定理，G有A到B的完备匹配，因A=B, 该匹配是完美匹配。 June 2016 12 June 2016 12 Department of Computer Science and Technology, Nanjing University Hall定理的推论 设二部图G是一个k-正则的(k  1), 则G有完美匹配. 证明. 不妨设G= < A, B, E>,k |A| =k |B| , 所以|A| =|B|. 下证G有A到B的完备匹配. 对任一S A，S与N(S)之间总共有k|S| 条边，而与 N(S)相关的边总共有k|N(S)| 条边。 ∴ k|S|  k|N(S)| ∴ |N(S)|  |S| 根据Hall定理，G有A到B的完备匹配，因 |A| = |B|， 该匹配是完美匹配