问题

对二元图 $G=(X,Y,E)$, 有

(1) $G$ 存在饱和 $X$ 中每个顶点的匹配的充要条件是
    \[
    |N(S)|\geqslant|S|,\quad\forall\ S\subset X.
    \]
    其中 $N(S)=\{v\in Y\mid \exists u\in S, u\ \text{与}\ v\ \text{相邻}\}$.

(2) $G$ 存在完美匹配的充要条件是
    \[
    |N(S)|\geqslant|S|,\quad\forall\ S\subset X.
    \]

(3) 若存在正整数 $t$, 满足 $\forall v\in X, d(v)\geqslant t$, $\forall u\in Y, d(u)\geqslant t$, 则存在饱和 $X$ 中每个顶点的匹配.

Remark:

基本概念:

点的邻域(neighborhood), 设 $x\in G$, 与 $x$ 相邻的所有顶点的集合记为 $\Gamma(x)$.

偶尔地, 称 $\Gamma(x)$ 为顶点 $x$ 的开邻域(open neighbourhood), 而将 $\Gamma(x)\cup\{x\}$ 称为 $x$ 的闭邻域(closed neighbourhood).

References:

赵静、但琦 主编《数学建模与数学实验》（第4版） P.102

GTM 184, Béla Bollobas, Modern Graph Theory