精选优质文档-倾情为你奉上第二节：Ramsey问题与Ramsey数1958年67月号美国数学月刊上登载着这样一个有趣的问题：“任何6个人的聚会，其中总会有3个互相认识或3人互相不认识。”这就是著名的Ramsey问题。以6个顶点分别代表6个人，如果两人相识，则在相应的两顶间连一红边，否则在相应的两顶点间连一蓝边，则上述的Ramsey问题等价于下面的命题：命题1.3.1 对6个顶点的完全图任意进行红、蓝两边着色，都存在一个红色三角形或一个蓝色三角形。证明 设是的6个顶点，与所连的5条边着红色或蓝色。由鸽巢原理知，其中至少有条边同色，不妨设与所连的3条边均为红色，如图1.3.1所示。若间有一条红边，不妨设为，则是一红色三角形。否则，间均为蓝边，即是一蓝色三角形。类似于命题1.3.1，还有如下的命题1.3.2命题1.3.4：命题1.3.2 对6个顶点的完全图任意进行红、蓝两边着色，都至少有两个同色三角形。证明 设是的6个顶点，由命题1.3.1知，对任意进行红、蓝两边着色都有一个同色三角形，不妨设是红色三角形，以下分各种情况
