小蓝书 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\) 条边，即 \[ a = \frac{1}{2}(n-1)(k+1) \] 同理，考虑 \(v_3\) 加入 \(A\) 得到的 \(n-1\) 个点有 \(a^{\prime} = 3^m + k = \frac{1}{2}(n-1)k\)
因为 \(a = a^{\prime} + 1\) ，所以 \[ \frac{1}{2}(n-1)(k+1)=\frac{1}{2}(n-1) k+1 \] 解得 \(n=3\)，矛盾，因此 \(v_1,v_3\) 相邻
同理 \(v_2,v_3\) 之间也有边，进而 \(v_1,v_2\) 与所有的 \(v_i(i=3,4,\cdots,n)\) 之间有边，故 \(G\) 是完全图 \[ 3^m = \frac{1}{2}(n-2)(n-3) \] 因此 \(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}\) 中的边 \[ \left(v_i, v_{i-m}\right),\left(v_i, v_{i-m+1}\right),\cdots,\left(v_i, v_{i-1}\right),\left(v_i, v_{i+1}\right), \cdots,\left(v_i, v_{i+m}\right) \quad 1 \le i \le 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\) 之间的握手总数为 \[ (3 k+6)(3 k+5-n)=(9 k-7) n \] 得到 \[ n=\frac{(3 k+6)(3 k+5)}{12 k-1} \] 从而 \[ 16 n=\frac{(12 k-1+25)(12 k-1+21)}{12 k-1} \] 显然 \(\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\) 的方阵 \[ \begin{array}{llllll} 1 & 2 & 3 & 4 & 5 & 6 \\ 6 & 1 & 2 & 3 & 4 & 5 \\ 5 & 6 & 1 & 2 & 3 & 4 \\ 4 & 5 & 6 & 1 & 2 & 3 \\ 3 & 4 & 5 & 6 & 1 & 2 \\ 2 & 3 & 4 & 5 & 6 & 1 \end{array} \] 对方阵中的每个点，它与同行、同列、同编号的 \(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=(V, E), V=\left\{v_1, v_2, \cdots, v_5\right\} \\[6pt]E=\left\{\left(v_1,~v_2\right),~\left(v_2,~v_4\right),~\left(v_3,~v_4\right),~\left(v_4,~v_5\right),~\left(v_1,~v_3\right)\right\} \]
画出 \(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
说明下面两个图是同构的。
解：
这玩意需要说明？
直接搬答案了，其实就是讲了一下哪个点对应哪个点什么的。
剩下的有空写吧，这几天效率怎么这么低。
