Hall定理11Hall定理(1935,MarriageTheorem)设二部图G=<V1,V2,E>,则G有V,到V2的完备匹配令对于任意的A≤V1，有IN(A)I≥IAI口证明.必要性易证，下证充分性（使用强归纳法）。如果1V11=1,充分性命题显然成立。假设当/V1/≤k(k≥1)时充分性命题均成立,要证：当/Vi/=k+1的充分性命题也成立。分二种情形来证明。(1)对Vi的任意真子集A，IN(A)I>|AI(2)存在Vi的一个真子集A'，IN(A)I=IA'I
Hall定理 11 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' |
Hall定理12归纳证明.(1)对V,的任意真子集A，IN(A)I>IAI任取一个顶点vEV任取wEN(v))（一定存在）H=G-{v,w)是一个二部图（非空）：H满足归纳假设的条件(N(A)最多少了一个w),从而H有V1-{v}到V2-{w}的完备匹配.这个匹配加上边(v,w)构成G的从V,到WV2的完备匹配
Hall定理 12 H满足归纳假设的条件(N(A)最多少 了一个w), 从而H有V1 -{v}到V2 -{w} 的完备匹配. 这个匹配加上边(v, w)构成G的从V1到 V2的完备匹配. v w 归纳证明. (1)对V1的任意真子集A , |N(A)| | A | 任取一个顶点v V1 , 任取wN({v}) （一定存在）. H=G-{v, w}是一个二部图（非空）