求教离散数学：证明任意一个具有6个顶点的简单图或其补图一定包含一个三角形.

题目

求教离散数学：证明任意一个具有6个顶点的简单图或其补图一定包含一个三角形.

答案

证明：

1)设6个顶点的图为G1,其补图为G2,则完全图G= G1∪G2.

2）对于完全图G,v1与其他5个顶点相连,设图G1用红色线表示,G2用蓝色线表示,对于V1与其他顶点相连的5条线中,用两种颜色表示的情况下,必有一种颜色的线大于等于3,如图所示,假设红色线数大于等于3.

3）图示中三条边（V2,V3）,（V3,V4）,(V2,V4),任意一条边为红色,则必存在一个三角形,如果这三条边都不为红色,则为蓝色,必有这三条蓝色边形成一个三角形.