[证] 我们来构造一个[tex=0.643x0.786]SBMIs+VUk7//BOpfqlQl0w==[/tex]阶图 [tex=0.786x1.0]4swj+MXBfXw/BCBdKDogfg==[/tex],图 [tex=0.786x1.0]4swj+MXBfXw/BCBdKDogfg==[/tex] 的项点代表[tex=0.643x0.786]SBMIs+VUk7//BOpfqlQl0w==[/tex] 个人，两个认识的人对应的顶点间连一条边, 从而图 [tex=0.786x1.0]4swj+MXBfXw/BCBdKDogfg==[/tex] 满足:对任意二顶点[tex=0.643x0.786]FeawaJGtBstYBxyU5e7M1g==[/tex]和 [tex=0.5x0.786]WThQ8iw4nU0wcEP44SeqUw==[/tex], 都有 [tex=9.214x1.357]NovbxKl63Ey/milqTcbe/wmqp0bxDx5/gnJMsDLPZ/Xidmd26VLr7VsTZQ9BOv3W8qb5XCUGlUlOYKN+j/H2hA==[/tex] ( 不包括[tex=1.357x1.0]jnHTrgGHcmhrR7Fi2sNknw==[/tex] 在内 )所求问题转化为，证明图 [tex=0.786x1.0]4swj+MXBfXw/BCBdKDogfg==[/tex]中存在一条 [tex=4.357x1.0]C6+SDlkDQWcIukVT9qB1Pg==[/tex] 路。为此，我们证明:对任意二顶点 [tex=0.643x0.786]FeawaJGtBstYBxyU5e7M1g==[/tex]和 [tex=0.5x0.786]WThQ8iw4nU0wcEP44SeqUw==[/tex],都有 [tex=9.214x1.357]NovbxKl63Ey/milqTcbe/wmqp0bxDx5/gnJMsDLPZ/Xidmd26VLr7VsTZQ9BOv3WcSa/hJyAyFTKf10mIUMkhLs3FQ3JklEmB/FYy86EyQE=[/tex]。分情况证明如下：1) 若 [tex=0.643x0.786]FeawaJGtBstYBxyU5e7M1g==[/tex]和[tex=0.5x0.786]WThQ8iw4nU0wcEP44SeqUw==[/tex]相邻 (即[tex=0.643x0.786]FeawaJGtBstYBxyU5e7M1g==[/tex] 和 [tex=0.5x0.786]WThQ8iw4nU0wcEP44SeqUw==[/tex]表示之二人认识），则有[tex=15.929x1.357]NovbxKl63Ey/milqTcbe/7wL4WC46tPoi6O3yENUmeamnhPOYw3hFrEKyUYsym1oo5ir5qlhBC8/I9FWk9odnia/HERWeB7EGVa20ibfPvk=[/tex]2) 若 [tex=0.643x0.786]FeawaJGtBstYBxyU5e7M1g==[/tex] 和[tex=0.5x0.786]WThQ8iw4nU0wcEP44SeqUw==[/tex] 不相邻 ( 即 [tex=0.643x0.786]FeawaJGtBstYBxyU5e7M1g==[/tex] 和 [tex=0.5x0.786]WThQ8iw4nU0wcEP44SeqUw==[/tex]表示之二人不认识）则仍有[tex=12.429x1.357]NovbxKl63Ey/milqTcbe/wmqp0bxDx5/gnJMsDLPZ/Xidmd26VLr7VsTZQ9BOv3WWXrwHLM3ZyKLUKPTeHdfmqrOMskkLA+le1Y8mDbx9ro=[/tex]否则，由已知[tex=9.214x1.357]V1D753We7vezsBlKQyfrUqxqYgT5ML4x4SEASQCkW1gDYudU09kvMlBhQZziDzeJCSPbKBklApY6Lf4CFRqEGA==[/tex] 知 [tex=9.214x1.357]NovbxKl63Ey/milqTcbe/wmqp0bxDx5/gnJMsDLPZ/Xidmd26VLr7VsTZQ9BOv3W2KOYhaJ/fjLGdJahqQSqZQ==[/tex]。那么, [tex=0.786x1.0]4swj+MXBfXw/BCBdKDogfg==[/tex]中除 [tex=0.643x0.786]FeawaJGtBstYBxyU5e7M1g==[/tex]和[tex=0.5x0.786]WThQ8iw4nU0wcEP44SeqUw==[/tex]外的余 [tex=1.929x1.143]Upz3IwbIEZiDQWxQtoLQyA==[/tex]个点, 每个顶点都恰与 [tex=0.643x0.786]FeawaJGtBstYBxyU5e7M1g==[/tex] 或 [tex=0.5x0.786]WThQ8iw4nU0wcEP44SeqUw==[/tex] 之一相邻。今考察其中一点 [tex=0.786x0.786]44SGfA2gQ2VZlXa1QKZD0Q==[/tex]设它与[tex=0.5x0.786]WThQ8iw4nU0wcEP44SeqUw==[/tex]相邻，则它必不与[tex=0.643x0.786]FeawaJGtBstYBxyU5e7M1g==[/tex]相邻。于是对于[tex=0.5x0.786]WThQ8iw4nU0wcEP44SeqUw==[/tex], [tex=0.786x0.786]44SGfA2gQ2VZlXa1QKZD0Q==[/tex]这一对顶点，它们都不与除去它们之后的 [tex=1.929x1.143]yNYO0++s0YwiOFYsKolaDA==[/tex] 个顶点中之一顶点 [tex=0.643x0.786]FeawaJGtBstYBxyU5e7M1g==[/tex]相邻，这就与题设条件：任二顶点合起来都与其余[tex=1.929x1.143]Upz3IwbIEZiDQWxQtoLQyA==[/tex] 个项点相邻, 相矛盾。  综合1）2），有[tex=4.357x1.0]C6+SDlkDQWcIukVT9qB1Pg==[/tex] 路的充分条件，可知图[tex=0.786x1.0]4swj+MXBfXw/BCBdKDogfg==[/tex]中存在着一条[tex=0.857x1.0]h610M+sGyf59WggKwaDo1Q==[/tex]路。[img=319x129]17861f2f5fd7ed8.png[/img]