饱和二部图

没有完美匹配的二部图G,若给它任意增加一条新的边,结果得到的二部图有完美匹配,则称图G是饱和的.设X■V(G),Γ(X)表示V(G)中与X中至少一个顶点相邻的所有顶点组成的集合.本文证明了一个二部图G=(U,W)是饱和的当且仅当(a)存在唯一X■U,使得X>Γ(X),X-1>Γ(X)且G的导出子图G[X∪Γ(X)]是完全二部图;(b)G的导出子图G[(U-X)∪(W-Γ(X))]是完全二部图,且满足U-X+1=W-Γ(X);(c)U-X中每个顶点与W中的每个顶点都相邻,且X∪(W-Γ(X))是图G的一个独立集.