MathLabs

第4题

十七个人彼此通信，每个人都与其余所有人通信。信件中只讨论三种不同主题，每一对通信者只讨论其中一个主题。证明至少有三个人彼此讨论同一个主题。
第 4/5 步：应用引理
上一步下一步
K6 uses at most two colors if no edge has color 1K_6\text{ uses at most two colors if no edge has color 1}
详细分析

若六个顶点之间有颜色1的边，它与 V1V_1 构成颜色1的三角形。否则这六个顶点的完全图只用另外两种颜色，由双色引理得到单色三角形。