爆难图论十六个点,每两点染上红黄绿三种颜色之一.问是否一定存在同色三角形?打错了……是每条边上色……

来源：学生作业帮助网编辑：作业帮时间：2024/05/11 00:55:25

爆难图论十六个点,每两点染上红黄绿三种颜色之一.问是否一定存在同色三角形?打错了……是每条边上色……
爆难图论
十六个点,每两点染上红黄绿三种颜色之一.问是否一定存在同色三角形?
打错了……是每条边上色……

爆难图论十六个点,每两点染上红黄绿三种颜色之一.问是否一定存在同色三角形?打错了……是每条边上色……
如果是完全图的话,设这16个点为V1,V2,V3,…,V16.
现考虑V1：除V1外还有15个点,而由V1引出的边共有15条,有抽屉原理知,
红黄绿三种颜色中至少有一种颜色,满足染上这种颜色的边数大于或等于15/3=5条.
不妨设这种颜色为颜色A.现考虑由V1引出的边中染上颜色A的边（≥5条）,任取其中5条边作为研究对象,不妨设5条边的两端点中除V1外的另一边分别为V2,V3,V4,V5,V6.由排列数知,这5点之间共连了10条边.下面分两种情况：
（1）若这10条边中存在一条边染上了颜色A,则由这条边的两端点及V1构成的三角形是同色三角形
（2）若这10条边中不存在染上颜色A的边,即这10条边中每条边都染上其余两种颜色（设为颜色B、C）中的一种.现在问题转化为：一个5阶完全图（共10条边）,每边都染上颜色B或C,证明此图中存在同色三角形.
不妨设V2与V3相连的边染上B,看下面的图片,共有四种情形：
①对情形一：边（V4,V5）非B即C,则V4和V5必与V2、V3之一构成同色三角形
②情形二与情形一相同
③对情形三：V2、V3、V4构成同色三角形
④对情形四：若边（V4,V5）,(V5,V6),(V4,V6)中存在一条染上C,显然存在同色三角形；若边（V4,V5）,(V5,V6),(V4,V6)均染上B,则V4、V5、V6构成同色三角形
综上所述,原图中必存在同色三角形.

爆难 图论十六个点,每两点染上红黄绿三种颜色之一.问是否一定存在同色三角形?打错了……是每条边上色……

爆难图论十六个点,每两点染上红黄绿三种颜色之一.问是否一定存在同色三角形?打错了……是每条边上色……