证明：设 $M$ 是 $2$ 部图 $G=(X\cup Y,E)$ 的最大匹配，则
$$
|M|=|X|-\max{|S|-|N(S)||\forall S\subseteq X}
$$
$\forall S\subseteq X$，$G$ 中任意一条边都至少与 $(X\backslash S)\cup N(S)$ 中的一点关联，由于每个点至多存在于匹配的一条边中，则
$$
|M|\le |X\backslash S|+N(S)=|X|-(|S|-N(S)) \tag{*}
$$
取 $X$ 中满足 $|S|-|N(S)|$ 最大的 $S$
考虑 $G_1=G[S\cup N(S)]$，$G_2=[(X\backslash S)\cup(Y\backslash N(S))]$
-
$G_1$ 中有饱和 $N(S)$ 的匹配 $M_1$
$\forall T\subseteq N(S)$，$|T|\le |N_{G_1}(T)|$，否则，记 $S^\prime= S\backslash N_{G_1}(T)$，有
$$
|S^\prime|-|N(S^\prime)|=|S|-|N_{G_1}(T)|-N(S)+|T|>|S|-N(S)
$$
与 $S$ 的最大矛盾
由 Hall 定理知成立
-
$G_2$ 中有饱和 $X\backslash S$ 的匹配 $M_2$
$\forall T\subseteq X\backslash S$，$|T|\le |N_{G_2}(T)|$，否则，记 $S^\prime= S\cup T$，有
$$
|S^\prime|-|N(S^\prime)|=|S|+|T|-N(S)-|N_{G_2}(T)|>|S|-N(S)
$$
与 $S$ 的最大矛盾
由 Hall 定理知成立
又 $M_1\cap M_2=\empty$，则 $M=M_1\cup M_2$ 是 $G$ 的匹配，且 $|M|=|M_1|+|M_2|=|X|-|S|+|N(S)|$，即 $|M|$ 取到了 (*) 式右边，故为最大匹配，证毕
证明：设 $M$ 是 $G$ 的最大匹配，$r=\max{o(G-S)-|S|:\forall S\subset V(G)}$，则 $|M|=\frac{1}{2}(|V(G)|-r)$
$\forall S\subset |V(G)|$，$G$ 的任意匹配 $M$，$M$ 在 $G-S$ 中的部分在 $o(G-S)$ 个奇分支中都有一点不能覆盖到，故这些点至少有 $o(G-S)$ 个。若这些点有些在 $M$ 中，则至少还有 $o(G-S)-|S|$ 个点没有匹配。故
$$
|M|\le \frac{1}{2}\Big(|V(G)|-(o(G-S)-|S|)\Big)\le \frac{1}{2}(V(G)-r)
$$
记 $R={v_1,\dots,v_r}$，考虑图 $H=\Big(V(G)\cup R,E(G)\cup K(V(G),R)\cup K(R)\Big)$，偶阶图
（Tutte 定理）
$\forall T\subseteq V$
$$
o(H-T)-|T|=o(G-T\cap V(G))-|T\cap V(G)|-r\le 0
$$
$H-T$ 是连通图，故 $o(H-T)\le 1$
当 $T=\empty$ 时，$n+r$ 是偶数（$n=o(G-S)个奇数+偶数(偶分支)+|S|\equiv r\mod 2$），故 $o(H-T)=0=|T|$
当 $T\neq \empty$ 时，$|T|\ge 1\ge o(H-T)$
综上， $H$ 满足 Tutte 条件，故存在 $H$ 的完美匹配 $M^\prime$，$|M^\prime|=\frac{1}{2}(n+r)$，删去与 $R$ 关联的边，至多删去 $r$ 条，得到 $G$ 的匹配 $M$，有 $|M|\ge \frac{1}{2}(n-r)$。故 $|M|=\frac{1}{2}(n-r)$ 为最大匹配
$G$ 的 $k$ 正则支撑子图称为 $G$ 的 $k$ 因子 k-factor。若 $G$ 存在边不交的 $k$ 因子 $G_1,\dots,G_t$ 使得 $G=G_1\oplus\cdots\oplus G_t$，则称 $G$ 是 $k$ 因子可分解 k-factorable。证明
(a) $G$ 含 $1$ 因子 $\Leftrightarrow$ $G$ 有完美匹配
(b) $K_{2n}$ 和 $K_{n,n}$ 是 $1$ 因子可分解的
(c) $K_{2n+1}$ 是 $2$ 因子可分解的
(d) 简单图 $G$ 是 $2$ 因子可分解的 $\Leftrightarrow$ $G$ 是 $2k$（$k\ge 1$）正则的
(e) Petersen 图是非 $1$ 因子可分解的
(f) 每个 $2k$（$k\ge 1$）正则图有 $2$ 因子分解 $\Leftrightarrow$ 每个 $k(\ge 1)$ 正则 $2$ 部图有 $1$ 因子分解
$G$ 的完美匹配就是 $G$ 的 $1$ 正则支撑子图，即为 $1$ 因子
由推论 5.1.2.3 知 $K_{2n}$ 有 $(2n-1)$ 个互不相交的完美匹配 $M_1,\dots,M_{2n-1}$，则 $K_{2n}[M_i]$ 是 $1$ 因子，且 $K_{2n}=K_{2n}[M_1]\oplus\dots \oplus K_{2n}[M_{2n-1}]$，则 $K_{2n}$ 是 $1$ 因子可分解
设 $K_{n,n}$ 划分为 $X={x_1,\dots,x_n}$ 和 $Y={y_1,\dots,y_n}$ 两部，设完美匹配
$$
M_i={(x_{a},y_{b}):a=1,\dots,n;b=a+i-1\mod n}\quad(i=1,\dots,n)
$$
则 $K_{n,n}[M_i]$ 是 $1$ 因子分解，且 $K_{n,n}=K_{n,n}[M_1]\oplus\cdots\oplus K_{n,n}[M_n]$，故 $K_{n,n}$ 是 $1$ 因子可分解
由 (d) 可得
$\Rightarrow$ 显然
$\Leftarrow$
设 $V(G)={v_1,\dots,v_n}$，由 $G$ 可以得到一个平衡 $k$ 正则定向图 $D$，构造二部无向图 $H=(P\cup Q,E)$，其中 $P={p_1,\dots,p_n}$，$Q={q_1,\dots,q_n}$，$E={p_iq_j:(x_i,x_j)\in E(D)或(x_j,x_i)\in E(D)}$，则 $H$ 是 $k$ 正则 $2$ 部图，由 (d) 中证明知 $H$ 有 $1$ 因子分解，$H$ 的 $1$ 因子对应 $G$ 的一个 $2$ 因子，故 $G$ 有 $2$ 因子分解
假设 Petersen 图是 $1$ 因子可分解的，那其能分解成 $3$ 个 $1$ 因子，则需将边划分成3部分，每部分边互不相邻。这相当于染色问题。通过枚举可知 Petersen 图不可 $3$ 边染色，矛盾，故 Petersen 图不是 $1$ 因子可分解的
左边为真命题，下证右边也是真命题
（归纳法）
- 当 $k=1$ 时，显然成立
- 假设 $k-1$ 时成立
由推论 5.1.1.2 和 (1) 知 $G$ 有 $1$ 因子，删去得 $k-1$ 正则 $2$ 部图 $G^\prime$，由归纳假设知 $G^\prime$ 是 $1$ 因子可分解，则 $G$ 是 $1$ 因子可分解
综上，由归纳法知右边成立
两边都是真命题，故两边等价
(a) 举例说明
(i) 定理 5.2.4 中条件“$d_G(x)+d_G(y)\ge n$ 不能改为“$d_G(x)+d_G(y)\ge n-1$”
(ii) 推论 5.2.4 中条件“$\delta(G)\ge \frac{n}{2}$”不能改为“$\lfloor\frac{n}{2}\rfloor$”
(iii) 定理 5.2.5 中的条件“$\kappa(G)\ge \alpha(G)$”不能改为“$\kappa(G)\ge \alpha(G)-1$”
(b) 利用定理 5.2.4 证明推论 5.2.4；利用定理 5.2.5 证明定理 1.7.2
$K_{1,2}$，$\alpha(G)=2,\kappa(G)=1$
$\alpha(G)\ge \kappa(G)$
$\alpha(G)\ge \kappa(G)$
不是 Hamilton
$\delta(G)\ge \frac{n}{2}\Rightarrow \forall x,y\in V(G),xy\notin E(G),d_G(x)+d_G(y)\ge n$，故满足 Ore 条件，由定理 5.2.4 知 $\alpha(G)\le \kappa(G)$
Ore 条件满足，由定理 5.2.4 知 $\kappa(G)\ge \alpha(G)$，由 定理 5.2.5 知，$G$ 是 Hamilton 图
设 $G$ 是 $n(\ge 3)$ 阶简单无向图。令 $T={x\in V(G):d_G(x)=n-1}$。证明：若 $|T|\ge \alpha(G)$，则 $G$ 是 Hamilton 图
任何分离集 $S$，有 $T\subseteq S$，则 $|T|\le \kappa(G)$，则 $\kappa(G)\ge \alpha(G)$，由定理 5.2.5 知 $G$ 是 Hamilton 图