关于图论里人互相认识的问题

2024-11-07 08:42:03

推荐回答（1个）

回答（1）：

这是由一道数学竞赛题改编过来的。
第一种情况：存在三人相互不认识，很显然结论是成立的。

第二种情况：任意三人中至少有两人认识。（这种情况就是原题）
抽象成点，全部连接，若认识边染成红色，否则染成蓝色。
由假设，这个图中没有蓝色三角形。

分两种情况。1，若某个顶点发出的蓝边至少有四条（以四条为例），那么分析就可知道存在存在红色的完全图K4；

2，若任一顶点发出的蓝线至多三条，那么存在某个顶点A的发出了（至少）六条边，然后在考察这六个顶点，在运用拉姆塞定理（二染色的K6中存在同色三角形），知道这六个顶点中存在红色的三角形。这三点再加A就是完全认识的人了。

以上就是问题解答的核心部分，细枝末节你就自己添加吧。