单色三角形问题damce sanjiaoxing wenti

属图论的一类问题，常在数学竞赛中出现.平面上n个顶点，每两个顶点间都有一条边相连的简单图叫做完全图，记作Kn，对Kn的所有的边进行着色，每条边着一种颜色，一共用m种颜色，m,n满足什么条件时有同一种颜色的三角形？这种类型的问题叫做单色三角形问题.
单色三角形问题最早出现在1947年的匈牙利数学奥林匹克试题中.原题是“证明在任何六个人中，总有三个人相互认识或互不认识.”1953年，美国普特南数学竞赛中，将同一问题改述为 “空间六点没有三点共线，也没有四点共面，连结每两点所得的15条线段中有一部分是红线，其余是蓝线. 求证存在一个同一颜色的三角形.”这是单色三角形名称的由来. 只要把第一个问题中的人看成点，两人互相认识，则对应的两点连一条红线，互相不认识，就连一条蓝线，就可以看出这两个问题实际上是一样的. 后来这一问题得到推广. 比如，1964年第6届IMO第4题： “17位科学家中每一位和其余16位通信，在他们的通信中共讨论三个问题，而任意两位科学家通信所讨论的是同一个问题. 证明至少有三位科学家通信所讨论的是同一问题.”
关于单色三角形，现有简单结论为：
❶双色完全图K₆中至少有两个不同的单色三角形.
❷双色完全图K₇中至少有四个单色三角形.
❸三色完全图K₁₇中至少有两个单色三角形.
❹四色完全图K₆₆中至少有一个单色三角形. 一般当m着色的完全图k n中有单色三角形时，若q= (m+1) (n-1) +2，则m+1着色的完全图K_q中至少有一个单色三角形.显见单色K₃，双色K₆，三色K₁₇，四色K₆₆等都可由这个公式递推得到.
此递推公式，由鸽笼原理不难证明.
K_q中任取一点v₀，由v₀引出的边有(m+1)(n-1)+1条，对这些边用m+1种颜色着色，由鸽笼原理，至少有一种颜色的边不少于n条.不妨设v₀出发有n条边都着红色，这n条边的另一端，n个顶点连成K_n，若K_n的边中有一条着红色，则这条边与v₀连成红色三角形.若Kn中没有一条边是红色，则K_n的边至多着m种颜色，由假设K_n中至少有一个单色三角形，这样无论如何m+1着色的Kq中都至少有一个单色三角形.