5
5.1.23
在圆周上放置 $n$ 个点, 其中 $n \ge k(k+1)$. 令 $G_{n,k}$ 为将每个点与两个方向上与它最近的 $k$ 个点相连得到的 $2k$-正则图. 例如, $G_{n,1}=C_n$, $C_{7,2}$ 如下图所示. 证明: 当 $k+1$ 能被 $n$ 整除时, $\chi(G_{n,k})=k+1$；当 $k+1$ 不能被 $n$ 整除时, $\chi(G_{n,k})=k+2$. 证明 $k \ge 2$ 时有 $\chi\!\left(G_{k(k+1)-1,\,k}\right) > k+2$, 由此证明上面结论中 $n$ 的下界不能被削弱.
任取圆上连续 $k+1$ 个点, 两两相邻, 构成团, 故
$\chi(G_{n,k})\ge k+1$. 若存在 $(k+1)$-着色,
则每串连续 $k+1$ 个点必须颜色各异, 绕圆一圈只能周期性出现
$1,2,\dots,k+1$. 因此只有当 $k+1\mid n$ 时才能完成 $(k+1)$-着色,
且此时用模 $k+1$ 的颜色 $c(i)\equiv i\pmod{k+1}$ 即得
$\chi(G_{n,k})=k+1$. 2) 上界 写 $n=q(k+1)+r$ ($1\le r\le k$) . 当 $n\ge k(k+1)$ 时有
$q\ge k\ge r$. 先把 $q-r$ 个整段用模式
$1,2,\dots,k+1$ 着色；余下 $r(k+2)$ 个顶点用
$1,2,\dots,k+1,k+2$ 的模式着色, 共重复 $r$ 次.
边界处最多与前后 $k$ 个邻点冲突, 而颜色有 $k+2$ 种, 故可行.
结合上一步得
$\chi(G_{n,k})=k+2$ (当 $k+1\nmid n$). 3) 若 $n=k(k+1)-1$ 仍想用 $k+2$ 色, 则某一色至少出现 $k$ 次,
其相邻两次出现的最小间距 $<k+1$.
但距离 $\le k$ 的两点相邻, 矛盾. 故
$\chi(G_{k(k+1)-1,k})>k+2$.
证明
5.1.33
证明: 任意图 $G$ 有一个顶点顺序使得贪心着色算法按照这个顺序着色时使用 $\Chi(G)$ 种颜色.
先排所有 $f$-色为 $1$ 的, 再排所有 $f$-色为 $2$ 的, $\ldots$, 最后排所有
$f$-色为 $\chi(G)$ 的. 记此顺序为 $$ v_1,v_2,\dots,v_n . $$ 对 $i$ 做归纳, 证明贪心算法给 $v_i$ 分配的颜色 $\le f(v_i)$. 1) $i=1$ 时显然成立. 2) 假设 $j<i$ 的都已成立, 即贪心给每个 $v_j$ 都用 $\le f(v_j)$ 的颜色.
考虑 $v_i$. 和 $v_i$ 同色的那些 $v_j$ (即 $f(v_j)=f(v_i)$), 在 $G$ 中不与 $v_i$ 邻接.
所以这些同色点不会与 $v_i$ 冲突. 于是, $v_i$ 的已着色邻点中, 其颜色最多只会出现在
$\{1,2,\dots,f(v_i)-1\}$ 里, 不可能出现到 $f(v_i)$.
因此贪心在给 $v_i$ 上色时最多只会用到 $f(v_i)$. 综上, 贪心在该顺序上最多用颜色 $\chi(G)$,
而 $\chi(G)$ 又是理论最少色数, 所以可以做到用 $\chi(G)$ 色.
证明
5.2.16
证明: r+1-团无关的任意 n-顶点简单图至多有 $(1-1/r)n^2/2$ 条边.
于是 $$ e(G)=\sum_{i<j} n_i n_j
=\frac12!\left(n^2-\sum_{i=1}^r n_i^2\right). $$ $
\sum_{i=1}^r n_i^2\ge r\bigl(\frac{n}{r}\bigr)^2=\frac{n^2}{r}
$,
等号当且仅当 $n_1=\cdots=n_r=n/r$.
代回得到 $$ e(G)\le \frac12\Bigl(n^2-\frac{n^2}{r}\Bigr)
=\Bigl(1-\frac1r\Bigr)\frac{n^2}{2}. $$ 当 $G$ 取为各部尽量均衡的完全 $r$ 部图时取等号.
证明
5.2.21
证明: 在所有 r+1-团无关的 n-顶点简单图中, Turan 图 $T_{n,r}$ 是唯一的边数达到最大值的图.
设 $G$ 为不含 $K_{r+1}$ 的极大边数图. 对任意不相邻顶点 $u,v$,
把 $v$ 的邻集改为 $N(u)$. 这不会产生 $K_{r+1}$, 且不减
边数. 对称化重复直到所有非邻点对都可对称, 得到 $G^\ast$.
标准结论: 若某一步出现 $e$ 严格增加, 则 $G$ 不是极大；因此极大时每一步都
保持等号, 从而 $G$ 已在每一步的等号条件下不变. 等号条件强制
所有非邻点属于同一独立集, 所有不同独立集之间完全相连, 于是
$G$ 已是完全 $r$ 部图
$
G=K_{n_1,\ldots,n_r},\ \sum n_i=n.
$ 完全 $r$ 部图的边数 $$ e(G)=\sum_{i<j}n_i n_j
=\frac12!\left(n^2-\sum_{i=1}^r n_i^2\right). $$ $
\sum n_i^2\ge r\bigl(\frac{n}{r}\bigr)^2,
$
且当且仅当 $n_1,\dots,n_r$ 两两相差不超过 $1$ 时取等.
因此若存在 $n_i\ge n_j+2$, 把一个顶点从较大的部移到较小的部会使
$\sum n_i^2$ 下降、$e(G)$ 上升, 矛盾. 故极值部大小必为 $\lfloor n/r\rfloor$ 或 $\lceil n/r\rceil$, 并且这是唯一的等号情形.证明