Department of Computer Science and Technology,Nanjing University Hal定理 Hall定理(1935，Marriage Theorem) 设二部图G=<V1,V2,E>,则G有V到V2的完备匹配分 对于任意的AsV1,有N(A)川≥A| ·证明.必要性易证，下证充分性（使用强归纳法)。 如果V1=1,充分性命题显然成立。 假设当V1k(k≥1)时充分性命题均成立，要证：当 V=k+1时充分性命题也成立。分二种情形来证明。 ()对V的任意真子集A,N(A)川>|A (2)存在V的一个真子集A',N(A")川=|A'I June 2016 9June 2016 9 Department of Computer Science and Technology, Nanjing University Hall定理 Hall定理(1935, Marriage Theorem) 设二部图G=<V1 , V2 , E>, 则G有V1到V2的完备匹配  对于任意的 A V1 ，有 |N(A)|  |A | 证明. 必要性易证，下证充分性（使用强归纳法）。 如果 |V1 |=1, 充分性命题显然成立。 假设当|V1 |k (k 1) 时充分性命题均成立, 要证:当 |V1 |=k+1时充分性命题也成立。分二种情形来证明。 (1)对V1的任意真子集A ， |N(A)|  | A | (2)存在 V1的一个真子集A'， |N(A')| = | A' |