作业帮 > 数学 > 作业

在任意六个人的聚会上,证明总有三个人互相认识或者总有三个人互不认识(这里认识是相互的,即甲认识乙,则乙一定认识甲)

来源:学生作业帮 编辑:神马作文网作业帮 分类:数学作业 时间:2024/11/17 11:15:13
在任意六个人的聚会上,证明总有三个人互相认识或者总有三个人互不认识(这里认识是相互的,即甲认识乙,则乙一定认识甲)
要过程,最好要用染色解决
在任意六个人的聚会上,证明总有三个人互相认识或者总有三个人互不认识(这里认识是相互的,即甲认识乙,则乙一定认识甲)
这是很经典的一道题啊.
要用染色的话,认识连红,不认识连蓝.
任选一个人,他和其他5人有一种颜色至少有三条,假设是红,并与ABC相连.
如果没有红色三角,那么ABC相互之间不能连红色.但是这样ABC就是蓝色三角形.
结论:至少有一个三边同色三角形.