2、贝尔热定理 定理1（贝尔热，1957G的匹配M是最大匹配，当且 仅当G不包含M可扩路。 证明：“必要性” 若G包含一条M可扩路P,则可令该可扩路为： P VOVIV26 V2kV2k+1 V2k-1 2k+1 显然，P中M中的边比非M中的边少一条。于是作新的匹配 M,它当中的边由P中非M中边组成。M,中边比M中多一条， 这与M是G的最大匹配矛盾。 V2k-1 V2k+1 100.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 10 2、贝尔热定理 定理1 (贝尔热，1957) G的匹配M是最大匹配，当且 仅当G不包含M可扩路。 证明：“必要性” 若G包含一条M可扩路P,则可令该可扩路为： P 012 2 2 1 k k v vv v v  L  显然，P中M中的边比非M中的边少一条。于是作新的匹配 M1,它当中的边由P中非M中边组成。M1中边比M中多一条， 这与M是G的最大匹配矛盾。 v0 v1 v2 v v2k-1 3 v4 v2k v2k+1 v0 v1 v2 v v2k-1 3 v4 v2k v2k+1