图论的证明题证明9个人中若非至少有4人互相认识,则至少有3个人互相不认识题目取自《图论与袋鼠结构》的习题中

来源：学生作业帮编辑：作业帮分类：数学作业时间：2024/06/01 12:09:01

图论的证明题
证明9个人中若非至少有4人互相认识,则至少有3个人互相不认识
题目取自《图论与袋鼠结构》的习题中

（1）.有某人认识的人少于5个,不认识的人至少有4个,如A不认识B,C,D,E.
如果B,C,D,E中有2人不认识,则他们与A,3个人互相不认识；
如果B,C,D,E都认识,则他们4人互相认识.
（2）.每个人认识的人不少于5个.
首先,9个人认识的人数的总和一定是偶数,因为若A,B认识,这个关系A在记数是计了1次,B在计数时也计了1次.每个关系对总和的贡献都是2.如果每个人恰认识5人,则9个人认识的人数的总和等于9*5=45,矛盾.
所以,至少有1个人A认识6人.由熟知的结果,这6人中或有3人互相不认识,或有3人互相认识,这3人与A,4人互相认识.
这是图论中的拉姆赛问题,本题就是证明拉姆赛数R(3,4)=9.
6人中或有3人互相不认识,或有3人互相认识,是拉姆赛数R(3,3)=6.

图论的证明题证明9个人中若非至少有4人互相认识,则至少有3个人互相不认识题目取自《图论与袋鼠结构》的习题中证明：在任何一个10人的小组中,或者有3人互相不认识,或者有4人互相不认识. 证明：任意28个人中,至少有3个人的属相相同. 用反证法证明13个人中至少有两个人的生日在同一个月有11个人,其中任何3人中有2人认识,证明在这11人中至少有一人认识其余10人中的5个人求证世界上任意六个人中,一定有三个人互相认识,或三个人互相不认识证明 400个人中至少有两个人生日相同 55个人参加一次考试,共有4道选择题,每题有3个选项.证明:必有3个人中有2个人的答案至少有3题相同. 证明6个人中或者存在3个人相互认识,或者存在3个人相互不认识一道图论题：一个旅行团中任意4位中至少有一个旅客认识另外3人,证明任意4人中有1人他早就认识旅行团中其余的每个人平面上有8条互相不平行的直线,证明:在所有的交角中,至少有一个角小于23度 4个人中,至少有2个人的生日同月的概率是________