定理8.12对于n个顶点图G,且8(G)>0, 则a1(G)+B1(G)=n 证明:(1)a1(G)+B1(G)≤n 设M是G的最大匹配,M|=β1(G)。设F是 关于M的未饱和点集合, (2)al(G)+β1(G)≥n 设L是G的最小边覆盖,L|=1(G)。令 H=G(L,H有n个顶点。又设M是H的最 大匹配,显然也是G的匹配,且McL。以 U表示H中关于M的未饱和点集合定理 8.12:对于n个顶点图G, 且(G)>0, 则1(G)+1(G)=n 证明:(1) 1(G)+1(G)n 设M是G的最大匹配, |M|=1(G)。设F是 关于M的未饱和点集合, (2) 1(G)+1(G)n 设L是G的最小边覆盖, |L|=1(G)。令 H=G(L), H有n个顶点。又设M是H的最 大匹配, 显然也是G的匹配,且 ML。以 U表示H中关于M的未饱和点集合