完全图禁同色路径
为了方便，设 $n$ 是 $24$ 的倍数。考虑一张 $n$ 个点的完全图，边分为红、蓝两种颜色。
若每条边的颜色都可以自由指定，构造性证明：存在一种指定颜色的方式，使得不存在长度大于 $2n/3$ 的同色链；
若固定 $n/2$ 条边的颜色，其余边的颜色可以自由指定，构造性证明：存在一种指定颜色的方式，使得不存在长度大于 $3n/4$ 的同色链。
题意
题解
1
将点集 $V$ 分为两部分 $V_1,V_2$，其中 $|V_1|=n/3, |V_2|=2n/3$。
令 $V_2$ 内部的边皆为蓝色，其余的边（至少一个端点属于 $V_1$）皆为红色。
蓝色链上的点必须都属于 $V_2$，因此长度不超过 $|V_2|-1=2n/3-1$；红色链不能连续经过两个 $V_2$ 上的点，因此长度不超过 $2|V_1|=2n/3$。故这种染色方案符合题目要求。
2
尝试用和 1 相同的方法。将点集 $V$ 分为两部分 $V_1,V_2$，其中 $|V_1|=n/4, |V_2|=3n/4$。我们保持“以 $V_1$ 中某个点为端点的边全为同种颜色（记为颜色 A）”这一条件，但允许 $V_2$ 内部也有一些（最初被固定为）颜色 A 的边。这种情况下，另一种颜色的链长度至多为 $3n/4$，但是颜色 A 的链长度需要单独分析。
设给定的 $n/2$ 条边的颜色中有 $r$ 个红，$b$ 个蓝。不妨设 $r\leq b$，因此 $r\leq n/4$。
若 $b\leq 3n/8$，则蓝色边的端点至多有 $3n/4$ 个，我们取这些点之外的任意 $n/4$ 个点为 $V_1$，并将红色作为颜色 A。由于 $r\leq n/4$，$V_2$ 中的红色边至多有 $n/4$ 条，故红色链长度不超过 $2|V_1|+n/4=3n/4$。
若 $b>3n/8$，令 $V_r$ 为所有指定为红色的边的端点组成的集合。称一条蓝边 $e$ 是好的，当且仅当其两个端点至少有一个属于 $V_r$。依次枚举所有好边，若其两个端点都不在 $V_1$ 中则将其任意端点加入 $V_1$，直到好边全部枚举一遍或 $|V_1|$ 到达 $n/4$。最终如果 $|V_1|<n/4$，则再将 $V\backslash V_r$ 中的其他任意一些点加入 $V_1$ 补齐 $n/4$ 个点。将蓝色作为颜色 A。
若好边的数量至少为 $n/4$，则至少 $n/4$ 条好边有一个 $V_1$ 内的端点，所以 $V_2$ 内部的蓝边至多有 $b-n/4\leq n/4$ 条，故蓝色链长度不超过 $2|V_1|+n/4=3n/4$。
若好边数量不足 $n/4$，则所有好边都有一个 $V_1$ 内的端点，故 $V_2$ 内部的蓝边都至少有一个端点属于 $V_r$。蓝色链不能连续经过两个 $V_2\backslash V_r$ 内的点，所以长度至多为 $2|V_1|+|V_r|+2\leq 3n/4$（因为 $|V_r|\leq n/4-2$）。
综上，这种染色方案符合题目要求。
Reference
Gerencsér, L., & Gyárfás, A. (1967). On Ramsey-type problems. Ann. Univ. Sci. Budapest. Eötvös Sect. Math, 10, 167-170.