作业帮 > 政治 > 作业

证明任意的9个人中一定有3个人互相认识或者有4个人互相不认识.

来源:学生作业帮 编辑:作业帮 分类:政治作业 时间:2024/07/14 04:08:31
证明任意的9个人中一定有3个人互相认识或者有4个人互相不认识.
我现在学的离散数学中的题,要用到图论基础.
思路估计是把人设为结点,而认识或不认识关系设为边...
共9个人,则A和8个人有关系
如果A至少和其中4个人认识,则这4人中只要有2人相互认识,满足3人认识;或者这4人互相不认识.
如果A和其中不足4人认识,则A至少和其中5人不认识……