六人中必有三人认识或不认识

问题：世界上任意六个人中，一定有三个人互相认识，否则就有三个人互相不认识。

据说，这是60年代的高中奥数题。我还是用图论的方法来证明吧

该问题的图论阐述

由于认识和不认识是一对互斥的概念，所以利用补图很容易将原问题转化为：

是否存在六个点的图，在它本身和它的补图中均不存在3-完全子图。如果不存在，则原问题得证

证明

1. 该六个点的图必然是连通图。

   如果不连通：

   若有一个孤立点，则剩余点必须两两相连，否则连接该孤立点和不相连的两点可构成补图中的一个3-完全图。

   若有2个及以上孤立点，则连接这两个点和剩余点中的任意一个可构成补图中的一个3-完全图。

2. 任取相连的两个点A、B。

   首先，在剩余的点中不存在同时与A、B相连的点。如果存在则构成3-完全图。

   由于是连通图，剩余的4个点可被分成与A相连和与B相连两个部分。不失一般性，设A为连接点较少的那个，分为以下三种情况：

   1) 没有点，2) 只有一个点，3) 有2个点，与A相连，那么任取与B相连的两点和A可构成补图中的一个3-完全图。

所以，综合上面所有的情况，不存在这样的六个点的图。所以原问题是成立的。