“充分性” 若不然，设M,是G的一个最大匹配，则M1>M。 令H=M△M。 Y1 Y2 Y3 Ya ys 容易知道：G山的每个分支或者是由M,与M中边交替 组成的偶圈，或者是由M与M中边交替组成的路。 在每个偶圈中，M,与M中边数相等；但因M>M, 所以，至少有一条路P,其起点和终点都是M非饱和点， 于是，它是G的一条M可扩路。这与条件矛盾。0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 11 “充分性” 若不然，设M1是G的一个最大匹配，则|M1|>|M|。 令H = M1ΔM。 y2 y3 y1 x1 x2 x3 x4 y4 x5 y5 容易知道：G[H]的每个分支或者是由M1与M中边交替 组成的偶圈，或者是由M1与M中边交替组成的路。 在每个偶圈中，M1与M中边数相等；但因|M1|>|M|， 所以，至少有一条路P，其起点和终点都是M非饱和点， 于是，它是G的一条M可扩路。这与条件矛盾