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. ·归纳：当U<=W以及U川=k且满足Hal条件时 ·从U任取一个节点子集，从W中取N(X),构造H:G-{X,N(X):H满足Hl条 件吗？ case1:对所有U的真子集S,均有|N(S)川>S引 取U中某个元素u,任取u的某个相邻元素w(u至少和 两个元素相邻) W · 构造H:G-{u,w,任取s子集，N(S)数量最多减少一个 均有H中的|N(S)川>=IS| 如果某个S,|N(S)川=S,上述推理哪里过不去？U W S u S W • 归纳：当|U|<=|W|以及|U|=k且满足Hall条件时 • 从U任取一个节点子集X，从W中取N(X) ，构造H:G-{X,N(X)}：H满足Hall条 件吗? • Case1：对所有U的真子集S，均有|N(S)|>|S| • 取U中某个元素u，任取u的某个相邻元素w(u至少和 两个元素相邻) • 构造H:G-{u,w}, 任取S子集，N(S)数量最多减少一个 • 均有H中的|N(S)|>=|S| 如果某个S，|N(S)|=|S|，上述推理哪里过不去？