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川=1，显然 你能想到用数学 归纳法证明吗？ ·假设：IU≤Wand1≤IU<k,结论成立 ·归纳证明要点： Let G be a bipartite graph with partite sets U and W,where k=UsW,such that Hall's condition is satisfied.We show that U can be matched to a subset of W. ·从U任取一个u,从N(u)中任取一个w,构造H:G-{u,w:H满足Ha条件吗？ ·如果对U的任意子集S,IN(S)川>IS引，是成立的。否则，很难看出 现在你能理解为什么在归纳证明中，需要分情形证明了吗？• 充分性 • 奠基: |U|=1,显然 • 假设： 结论成立 • 归纳证明要点： • 从U任取一个u，从N(u)中任取一个w，构造H:G-{u,w}：H满足Hall条件吗? • 如果对U的任意子集S，|N(S)|>|S|,是成立的。否则，很难看出 你能想到用数学 归纳法证明吗？ 现在你能理解为什么在归纳证明中，需要分情形证明了吗？