PS 5

Problem 1

Task 1

n = 1, 2的情况是 trivial 的，下面用数学归纳法对 n 作归纳证明

假设上述命题对所有 的情况成立，下面证明对任意 的图，这个命题也成立。

对一个阶数为 k + 1的图G及其补图 ，考虑其中的任一顶点 v与剩下k个顶点组成的图 ，记 ，由归纳假设有 。

1. 若顶点 只让 中至多一个的染色数加一（显然至多加一），则显然有

满足归纳假设 2. 如若不然，则 同时使 的染色数加一，这蕴含

而又由补图性质

这表明

故

同样满足归纳假设

综上，题设对k+1的情况亦成立，归纳出其总成立，证毕

Task 2（只要均匀的给两边加 就好了）

基于等式 1，由均值不等式，满足这一条件必须有

自然的要求是 n为奇数

考虑下面的构造：从单点开始，对G依次以下述规则添加顶点：当已有顶点数为奇数时，添加一个与之前所有点建边的顶点，当已有顶点数为偶数 (including 0) 时，添加一个与之前所有点不建边的顶点

通过这样的构造，在 中 1, 2, 4, … , n-1 构成一个大小为 的 clique，而 1, 3, 5, …, n 构成一个大小为 的独立集，从而在 中构成一个大小为 的 clique。因此

由Task1夹逼出

Problem 2

不正确，考虑下面的反例 构造一个 ，其中 构成一个 ，而 与 建边

此时显然 ，唯一的着色方案为对 至 采用不同的颜色，而 的颜色和 相同

注意到 构成一个独立集，而由于 中每个点都和8个点建边，不可能有包含其中顶点且大小大于2的独立集，所以最大的独立集大小即为5， 且唯一满足条件的集合为 ，由前面的讨论知这个集合的每个点颜色都不相同，而

故结论不成立！(示意图如下)

Problem 3

由Hall-marriage定理可得，存在一系列 的子集 ，下面考虑其中 cardinal 最小的集合，记为

最小的亏集自然的推论为，任给 ，

1. 若 ，任意card为 的子集 ，其 必然为 的子集，故

矛盾，因此必有(i)成立 2. 若存在一个 ，记其在 建边的点为 ，则若把 删去

矛盾，从而(iii)亦成立

下面考察(ii)

若上面的 已满足(ii)，自然已解决，如若不然，即

这时 必然是 的子集，故有 也是一个亏集，且

此时考虑 子集集合中的最小亏集即题目所求，故这样的集合总存在

Problem 4

考虑建立 bipartite ，建边要求为

那么题目化归为寻找 的一个 perfect matching

注意到由于 各自互不相交，故 ， ，由鸽巢定理得到，故由Hall-Marriage定理可得这个perfect matching必然存在