第3题

考虑空间中的9个点，且任意4点不共面。每对点连一条红色、蓝色或不着色的边。求最小整数

n

，使得恰好染色

n

条边时必存在三条边同色的三角形。

第 3/4 步：检查在一个方形取两个顶点的三角形

通俗地说

检查在一个方形取两个顶点的三角形

i\equiv j\pmod2\Longrightarrow \chi(R_iR_j)=0

详细分析

考虑 $R_iR_jB_k$ 。若 $i\equiv j\pmod2$ ，边 $R_iR_j$ 是不着色的对角线；否则 $R_iB_k$ 与 $R_jB_k$ 颜色相反。对 $B_iB_jR_k$ 同理，故不存在单色三角形。