01.md

1.3.12

题目

证明：设 $G$ 是顶点集 $V={x_1,x_2,\dots.x_n}$ 且不含子图 $K_{r+1}$ 的简单无向图，则存在顶点集为 $V$ 的完全 $r$ 部图 $H$ 使得对每个 $i (1\le i\le n)$ 均有 $d_G(x_i)\le d_H(x_i)$ 并且等号成立 $\Leftrightarrow G\cong H$。

答案

（归纳法）

• 当 $r=1$ 时，显然成立

• 假设 $r-1$ 时成立

设最大度为 $\Delta$，取一最大度点 $x$，设 $G_x=G[N_G(x)]$

由题设 $K_{r+1}\not\subseteq G$，因而有 $K_r\not\subseteq G_x$，否则 $K_{r+1}\subseteq G[N_G(x)\cup{x}]$，矛盾

由归纳假设，存在 $N_G(x)$ 上的完全 $r-1$ 部图 $H^\prime$ 使得 $\forall u\in N_G(x),d_{G_x}(u)\le d_{H^\prime}(u)$

构造 $H=(V,E)$，其中 $E=E(H^\prime)\cup E\left(K_{N_G(x),V\backslash N_G(x)}\right)$

$H$ 满足题设 $$ d_H(v)=|N_G(x)|=\Delta\ge d_G(v) \quad \forall v\in V\backslash N_G(x)\ d_G(v)=d_{G_x}(v)+|N_G(v)\cap (V-N_G(x))|\le d_{H[N_G(x)]}+|V-N_G(x)|=d_H(x) \quad \forall v \in N_G(x) $$

综上，由归纳法知命题成立

对于 $=$

$\Leftarrow$，显然

$\Rightarrow$，（归纳法）

• 当 $r=1$ 时，显然成立
• 假设 $r-1$ 时成立

$G$ 中 $\forall v\in V\backslash N_G(x)$，$v$ 全部与 $V\backslash N_G(x)$ 中点相连（$d(v)=\Delta$）

$\forall v\in N_G(x),d_{G_x}=d_{H[N_G(x)]}$，则由假设知 $G_x$ 是完全 $r-1$ 部图，则其再与 $V-N_G(x)$ 中点全部点相连，就成了 $V$ 上完全 $r$ 部图

Theorem 5.1

题目

设 $G$ 是简单无向图，$\delta = \delta(G) \ge 2$，则 G 中含长至少为 $\delta+1$ 的圈。

解答

令 $P=(x_0,x_1,\dots,x_k)$ 是 $G$ 中最长路。

由 $P$ 的最长性，$N_G(x_0)\subseteq {x_1,\dots,x_k}$。

令 $i=\mathop{\arg\max}_{i} x_0x_i \in E(G)$，则有 $i\ge \delta$。

故 $C = (x_0,x_1,\dots,x_i,x_0)$ 就是长至少为 $\delta + 1$ 的圈

1.4.3

题目

证明：设 $D$ 是简单图，且 $k=\max{\delta^+,\delta^-}$，则 $D$ 中含长至少为 $k$ 的有向路

解答

令 $P=(x_0,x_1,\dots,x_n)$ 是 $G$ 中最长有向路。

由 $P$ 的最长性，$N_D^+(x_n)\subseteq {x_0,\dots,x_{n-1}}$，$N_D^-(x_0)\subseteq {x_1,\dots,x_n}$

所以 $$ n\ge \max\left{\left|N_D^+(x_k)\right|,\left|N_D^-(x_0)\right|\right} \ge \max\left{\delta^+,\delta^-\right}=k $$ 即 $D$ 中含长至少为 $k$ 的有向路