小蓝书 17.1 题解
传送门：小蓝书 17.1
第一部分 例题
例1
某聚会有 $605$ 个人参加，已知每个人至少和其余的一个人握过手
求证：必有一个人至少和其中两个人握过手。
解：
本题最特别的就是这个 $605$ 了，我们注意到它是奇数。
考虑反证法，如果每个人都至多和其中一个人握过手，图就变成了这个样子：
设边数为 $m$ ，则节点数为 $2m$ ，这是个偶数，与 $605$ 是奇数矛盾，故原命题成立。
例2
能否让马跳动几次，将下图一所示的阵势变为图二？
提示：看图三，
知道要干嘛了吧。
解：
先把每个格子编号，然后把每个马能跳到的地方都连上，如图所示
显然，两幅图中的马无论怎么跳都不会改变相对顺序，因此不可能。
例3
有 $n(n \ge 3)$ 个人，他们之间有些人互相认识，有些人互相不认识，且至少有一个人没有与其他人都认识
问：与其他人都认识的人数的最大值是多少？
解：
注意，这里没有与其他人都认识，不代表这个人一个都不认识。
考虑作无向图 $G$ ，两点相邻当且仅当他们互相认识。
因为要最大值，所以有且仅有一个人没有与其他人都认识。
由此可得，至少有两个点不相邻。设 $v_1,v_2$ 之间没有边 $e = (v_1,v_2)$ 。
则图 $G$ 的边数最多时图形为 $K_n - e$ ，即完全图 $K_n$ 中去掉边 $e$ 后所得的图。
从而与其他节点都相邻的节点个数的最大值为 $n-2$ ，也就是答案。
例4
九名数学家在一次国际数学会议上相遇，
发现他们中的任意三个人中，至少有两个人可以用同一种语言对话。
如果每个数学家至多可说三种语言，求证至少有三名数学家可以用同一种语言对话。
解：
翻译成图论的语言，就是任意 $3$ 个点之间至少有一条边，且每个点的至多有 $3$ 种不同颜色的边。
要证明的是：图 $G$ 中存在 $3$ 个点，他们两两相邻，且这三条边具有相同的颜色（不妨称为同色三角形）
接下来我们来寻找一些性质。如果三个点 $v_i,v_j,v_k$ 有同色的边 $(v_i,v_j),(v_i,v_k)$ ，则一定有同色 $(v_j,v_k)$ 。
这说明同色边具有一种传递性。因此我们分类讨论 $v_1$ 的不同情形：
点 $v_1$ 与其他所有点都相邻。根据抽屉原理，至少有两条边具有相同的颜色。
点 $v_1$ 与其他所有点，至少有一个点不相邻。不妨设 $v_1$ 与 $v_2$ 不相邻。
由于每三个点之间至少有一条边，所以剩余 $7$ 个点发出的，另一个端点是 $v_1$ 或 $v_2$ 的边至少也有 $7$ 条
那么为了 $v_2$ 不构成同色三角形（如果不行就证明一定存在了不是吗），$v_2$ 要尽可能连更多的剩下的 $7$ 个点
而每个点只能出 $3$ 种颜色的边，因此 $v_2$ 至多连上 $3$ 个点，或者说 $v_1$ 至少有 $4$ 个点与它相邻。
根据抽屉原理，这连接 $4$ 个点的 $4$ 条边中，一定有 $2$ 条是同色的。
至此，我们证明了原命题。
另外，小蓝书还提到了 $n=8$ 时该命题的一个反例（数字表示边的颜色）
例5
有 $n$ 名选手 $A_1,A_2,\cdots,A_n$ 参加数学竞赛，
其中有些选手是互相认识的，而且任何两个不相识的选手都恰好有两个共同的熟人。
若已知选手 $A_1$ 与 $A_2$ 互相认识，但他俩没有共同的熟人，证明他俩的熟人一样多。
解：
翻译成图论的语言：
$n$ 个点的无向图 $G$ 中，任意两个不相邻的点 $v_i,v_j$ ，都存在恰好两个点 $a,b$ 满足 $v_i,v_j$ 分别同时与 $a,b$ 相邻。
已知 $v_1,v_2$ 相邻，且不存在点 $u$ 满足 $(v_1,u)$ 和 $(v_2,u)$ 同时存在，求证： $v_1$ 与 $v_2$ 的度数相同。
解法1：之所以分成两个解法，是因为我有个比较直观的解法，放在解法2讲。
考虑记 $N(v_1)$ 为 $v_1$ 的邻域，即 $\forall v_i \in N(v_1),\exists (v_i,v_1)\in G$ ，并记 $N(v_2)$ 为 $v_2$ 的邻域。
若在 $N(v_1)$ 中除 $v_2$ 外还有点 $v_i$ ，则 $v_i \not\in N(v_2)$ 。否则 $A_1$ 与 $A_2$ 有共同的熟人 $A_i$ 。
于是 $v_2$ 与 $v_i$ 除 $v_1$ 外还应有一个与它们共同相邻的点 $v_j$ ，则 $v_j \in N(v_2)$ ，如图所示。
对于 $N(v_1)$ 中不同于 $v_2$ 的点 $v_i,v_k$ ，他们不可能与 $N(v_2)$ 中除 $v_1$ 外的一点 $v_j$ 都相邻。
否则，两个不相邻的节点 $v_1,v_j$ 有三个共同相邻的节点 $v_2,v_i,v_k$ 。
因此对于 $N(v_1)$ 中不同于 $v_i$ 的点 $v_k$ ，一定在 $N(v_2)$ 中存在不同于 $v_j$ 的相邻点 $v_l$ 。
由此可得 $|N(v_1)| \le |N(v_2)|$ ，同理亦可得 $|N(v_1)| \ge |N(v_2)|$ ，即 $|N(v_1)| = |N(v_2)|$ 。$\square$
解法2：
其实和解法1是一个原理，但是我是从图形角度硬看出来的，可以说是“无字证明”吧。
先假设 $n$ 为偶数。设 $i \in N(v_1),~j\in N(v_2)$ ，如果 $i,j$ 相邻，那只有左边那种情况。
如果 $i,j$ 不相邻，那么只可能是右边那种情况，然而这很明显是错的（应该懂我的意思吧）
那么所有非 $i$ 的 $x\in N(v_1)$ 都能这么推导出来，反过来也一样，我们得到了偶数情况成立的事实。
考虑奇数的情况，这个很简单，无论你怎么在原图上加一个点，都会出错，所以也是成立的。证毕。
感觉这个解法很符合我对 OI 的理解，举不出反例不就是对的嘛。（大雾）
例6
有 $n$ 个人，一直他们中的任意两人至多通电话一次，
他们中任意 $n-2$ 个人之间通电话的总次数相等，都是 $3^m$ 次，其中 $m$ 是自然数。求 $n$ 的所有可能值。
解：任意两点间至多有 $1$ 条边，任意 $n-2$ 个点构成的子图都恰好有 $3^m$ 条边。
显然 $n\ge 5$ 。设任意一条边为 $(v_1,v_2)$ ，并设 $v_1$ 与 $v_3$ 不相邻。
接着分别考虑以下三个由 $n-2$ 个点构成的子图：
- 由 $v_1,v_4,v_5,\cdots,v_n$ 构成的子图，记为 $A$ 。
- 由 $v_2,v_4,v_5,\cdots,v_n$ 构成的子图，记为 $B$ 。
- 由 $v_3,v_4,v_5,\cdots,v_n$ 构成的子图，记为 $C$ 。
由题意可知 $A,B,C$ 的边数相等，这意味着 $v_1,v_2,v_3$ 分别与 $v_4,v_5,\cdots,v_n$ 之间的连边总数相等，记为 $k$ 。
将 $v_2$ 加入 $A$ 中，则这 $n-1$ 个点之间的边的总数为 $a = 3^m + k + 1$ 。
再从这 $n-1$ 个点中去掉一点，剩下的 $n-2$ 个点所连的边数都是 $3^m$
这意味着每个点都与其余 $n-2$ 个点连 $k+1$ 条边，即
同理，考虑 $v_3$ 加入 $A$ 得到的 $n-1$ 个点有 $a^{\prime} = 3^m + k = \frac{1}{2}(n-1)k$
因为 $a = a^{\prime} + 1$ ，所以
解得 $n=3$，矛盾，因此 $v_1,v_3$ 相邻
同理 $v_2,v_3$ 之间也有边，进而 $v_1,v_2$ 与所有的 $v_i(i=3,4,\cdots,n)$ 之间有边，故 $G$ 是完全图
因此 $n=5$ 。
例7
设 $n$ 为一正整数，且 $A_1,A_2,\cdots,A_{2n + 1}$ 是某个集合 $B$ 的子集。设
- 每一个 $A_i$ 恰含有 $2n$ 个元素。
- 每一个 $A_i \cap A_j(1 \le i < j \le 2n + 1)$ 恰含有一个元素。
- $B$ 的每个元素至少属于 $A_i$ 中的两个。
问对怎样的 $n$ ，可以将 $B$ 中元素各标上数 $0$ 或 $1$ ，使得每个 $A_i$ 恰好含有 $n$ 个标上了 $0$ 的元素？
解：可以发现，第二个条件恰好可以建图。
不过在此之前，我们先修正第三个条件：认为 $B$ 的每个元素恰好属于 $A_i$ 中的两个。
因为如果有一个元素 $a_1\in A_1\cap A_{2n}\cap A_{2n + 1}$ ，那么剩下的 $2n-2$ 个子集每个至多含 $A_1$ 中一个元素
从而 $A_1$ 中至少有一个元素不属于 $A_2\cup A_3\cup\cdots\cup A_{2n-1}\cup A_{2n}\cup A_{2n+1}$ ，这与第三条矛盾。
考虑作完全图 $K_{2n+1}$ ，每一个节点 $v_i$ 表示一个子集 $A_i$ ，每一条边 $(v_i,v_j) = b_{i,j}$ 表示 $A_i,A_j$ 的交
于是题目就转化为：对怎样的 $n$ ，可以给 $K_{2n+1}$ 的每条边贴一个 $0$ 或 $1$ 的标签
使得图中任意一点 $v_i$ 出发的 $2n$ 条边中恰有 $n$ 条边贴有 $0$ 的标签。
因为 $K_{2n+1}$ 有 $n(2n+1)$ 条边，如果上述条件能被满足，则标 $0$ 的边共有 $\dfrac{1}{2}n(2n+1)$ 条，$n$ 必须为偶数
反之，若 $n=2m$ 是偶数，我们把 $K_{2n+1}$ 中的边
全部标上 $0$ ，其余的全部标上 $1$ ，则满足题目要求的贴标签方法（注意，下标按模 $2n+1$ 进行）
综上，当且仅当 $n$ 为偶数时，可以满足题目要求。
例8
有 $12k$ 人参加会议，每人都恰好与 $3k+6$ 人握过手，
并且对其中任意两人，与这两个人都握过手的人数皆相同，问有多少人参加会议？
解：
设对任意两人，与他们握过手的有 $n$ 人。
考虑某个 $a$ ，与 $a$ 握过手的全体记为 $A$ ，与 $a$ 没有握过手的全体记为 $B$ 。显然 $|A| = 3k + 6,|B| = 9k-7$ 。
设 $b \in A$ 。与 $a,b$ 都握过手的 $n$ 个人都在 $A$ 中，因此 $b$ 与 $A$ 中的 $n$ 个人握手，与 $B$ 中 $3k+5-n$ 个人握手。
设 $c\in B$ ，与 $a,c$ 都握过手的 $n$ 个人都在 $A$ 中，于是 $A$ 与 $B$ 之间的握手总数为
得到
从而
显然 $\gcd(3,~12k-1) = 1$ ，则 $(12k-1) \mid 25\times 7$ 。
又因为 $(12k-1) \bmod 4 = 3$ ，所以 $12k-1 = 7,~5\times 7,~5^2\times 7$ 。
经检验，只有 $12k-1=5\times 7$ 产生整数解 $k=3,~n=6$ 。
到这里这题就解出来了，但是小蓝书还贴心的给出了构造：
构造一个由 $36$ 个点组成的图，图中每个点引出 $15$ 条边，且对每一对点与他们相连的点均为 $6$ 个。
自然地，我们可用 $6$ 个完全图 $K_6$ 。把 $36$ 个点分成 $6$ 组，同组的 $6$ 人编号，排成一个 $6\times 6$ 的方阵
对方阵中的每个点，它与同行、同列、同编号的 $15$ 个点相连，与其余点不相连
容易发现，与任意两个人都握过手的恰好有 $6$ 人。（这个图画的还是挺巧妙的）
例9
给定整数 $m\ge 2$ ，一次会议共有 $3m$ 人出席，每两人之间或者握手一次，或者不握手。
若存在其中的 $n(n\le 3m-1)$ 个人，他们握手的次数分别为 $1,2,\cdots,n$ ，则称这次会议是 “ $n-$有趣的 ”
若对一切可能发生的 $n-$有趣的会议，总存在 $3$ 名参会者两两握过手，求 $n$ 的最小值。
解：将 $3m$ 人分别记为 $A_1,A_2,\cdots,A_{3m}$ 。
当 $1 \le n \le 2m$ 时，我们构造如下 $n-$有趣的会议：
对 $i$ 从 $1$ 到 $m$ ，令 $A_{3m+1-i} $与 $A_i,A_{i+1},\cdots,A_{2m}$ 握手，如图所示
此时，$A_1,A_2\cdots,A_m,A_{2m+1},A_{2m+2},\cdots,A_{3m}$ 握过手的次数分别是 $1,2,\cdots,2m$
注意到 $2m \ge n$ ，这是一个 $n-$有趣的会议。
对任意 $3$ 名参会者，必存在两人同时属于 $S_1 = \left\{A_1, A_2, \cdots, A_{2 m}\right\}$ ，
或同时属于 $S_2 = \left\{A_{2 m+1}, A_{2 m+2}, \cdots, A_{3 m}\right\}$ ，由图构造可知他们两人没有握手。
从而不存在 $3$ 名参会者两两握过手。由此可知 $n \ge 2m+1$ 。
另一方面，当 $n=2m+1$ 时，考虑任意 $(2m+1)-$有趣的会议。
该会议中存在一人恰好握过 $2m+1$ 次手，不妨设 $A_{3m}$ 恰与 $A_1,A_2,\cdots,A_{2m+1}$ 这 $2m+1$ 人握过手。
记 $T_1=\left\{A_1, A_2, \cdots, A_{2 m+1}\right\},~T_2=\left\{A_{2 m+2}, A_{2 m+3}, \cdots, A_{3 m}\right\}$
由于 $T_2$ 中的人的握手次数至多取到 $\{m, m+1, \cdots, 2 m+1\}$ 中的 $m-1$ 个不同值
故存在一个数 $k$ 满足 $m \le k \le 2m+1$ 且不是 $T_2$ 中任何一人的握手次数。
这意味着 $T_1$ 中必有一人的握手次数为 $k$ ，设他为 $A_i$ 。
由于 $A_i$ 与 $T_2$ 中的人的握手次数不超过 $m-1$ ，
故 $T_1$ 中存在一人 $A_j(\ne A_i)$ ，与 $A_i$ 握过手，这样 $A_{3m},A_i,A_j$ 两两握过手。
从而，在任意一个 $(2m+1)-$有趣的会议中，总存在 $3$ 名参会者两两握过手。
综上可知， $n$ 的最小值为 $2m+1$ 。
第二部分 习题
题1
设图
画出 $G$ 的图形。
解：
画图，很简单。
题2
设图 $G=(V, E)$ 是简单图， $|V|=n,~|E|=e$ ，求证 $e \le \frac{n(n-1)}{2}$ 。
解：
这难道不是显然吗？
简单图每条边与两个不同节点关联，且每两个节点之间至多有一条边。
那么边数至多是 $\binom{n}{2} = \frac{n(n-1)}{2}$ ，而简单图不一定是完全图，因此 $e \le \frac{n(n-1)}{2}$
题3
说明下面两个图是同构的。
解：
这玩意需要说明？ 直接搬答案了，其实就是讲了一下哪个点对应哪个点什么的。
剩下的有空写吧，这几天效率怎么这么低。
