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

Question

是《图论与代数结构》里的第一章练习题第6题。
证明9个人中若非至少有4个人互相认识，则至少有3个人互相不认识。
再问一下，如果说4个人互相认识，反映在图上，应该是把连接4个点的道路或者回路还是K4图啊？这个问题没搞清楚……

Answer 1

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

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

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

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

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