MathLabs

第4题

十七个人彼此通信，每个人都与其余所有人通信。信件中只讨论三种不同主题，每一对通信者只讨论其中一个主题。证明至少有三个人彼此讨论同一个主题。
第 3/5 步：选取六个同色邻点
上一步下一步
⌈163⌉=6\left\lceil\frac{16}{3}\right\rceil=6
详细分析

按主题给每一对人连边着色。从任意的人 V1V_1 出发的十六条边只有三种颜色，因此至少有六条同色，设为颜色1。