Question

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

Answer 1

证明：

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

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

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