图论及其应用的内容简介
《图论及其应用(第3版)》既可用作高校数学系、应用数学系、计算机科学系、电子学系、自动化系、管理科学系和相关的研究所的研究生和高年级本科生选修课教材，也可用作高校和研究所从事相关专业的教师和研究人员以及图论工作者的参考书。着眼于有向图，将无向图作为特例，在一定的深度和广度上系统地阐述了图论的基本概念、理论和方法以及基本应用。
关于图论里人互相认识的问题
这是由一道数学竞赛题改编过来的。
第一种情况：存在三人相互不认识，很显然结论是成立的。
第二种情况：任意三人中至少有两人认识。（这种情况就是原题）
抽象成点，全部连接，若认识边染成红色，否则染成蓝色。
由假设，这个图中没有蓝色三角形。
分两种情况。1，若某个顶点发出的蓝边至少有四条（以四条为例），那么分析就可知道存在存在红色的完全图K4；
2，若任一顶点发出的蓝线至多三条，那么存在某个顶点A的发出了（至少）六条边，然后在考察这六个顶点，在运用拉姆塞定理（二染色的K6中存在同色三角形），知道这六个顶点中存在红色的三角形。这三点再加A就是完全认识的人了。
以上就是问题解答的核心部分，细枝末节你就自己添加吧。
图论及其应用的介绍
《图论及其应用》由徐俊明所著，中国科学技术大学出版社于2010年3月1日正式出版。全书内容共分7章，包括Euler回与Hamilton圈，树与图空间，平面图，网络流与连通度，匹配与独立集，染色理论，图与群以及图在矩阵论、组合数学、组合优化、运筹学、线性规划、电子学以及通讯和计算机科学等多方面的应用，每章分为理论和应用两部分。
