欧阳维诚

匈牙利是世界上开展中学生数学竞赛最早的国家．匈牙利全国中学生数学竞赛中有这样一道试题：

证明：在任何６个人中，一定可以找到３个互相认识的人，或者３个互不认识的人．

这个问题乍看起来，似乎令人难以想像．若店中坐着６位客人，萍水相逢，全是他乡之客，我们凭什么能够判断他们之中，必有３个人互相认识，或者３个人互不认识呢？这个问题用数学方法来证明却出人意料地简单．

为简单直观起见，我们用平面上的６个点Ａ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ来代表６个人，如果两人互相认识，就在代表他们的两点之间连一条线；如果两人互不认识，则不连线．这样就会得到一个由一些点和线组成的图．

现在从６个人中随便挑出一个人，比方说是Ａ吧，其余５个人中，或者与Ａ认识，或者与Ａ不认识．不妨假定：与Ａ认识的人有３个（否则与Ａ不认识的人就至少有３个，把“与Ａ认识”换成“与Ａ不认识”即可），例如，Ｂ、Ｃ、Ｄ与Ａ认识，如图１所示，ＡＢ、ＡＣ、ＡＤ之间就连有一条线．

再看Ｂ、Ｃ、Ｄ三人，如果他们彼此都不认识，那么我们就在６个人中找到了３个互不认识的人，本题的结论成立．如果Ｂ、Ｃ、Ｄ中至少有两人互相认识，例如Ｂ与Ｃ互相认识，那么Ｂ与Ｃ之间就要连一条线，这时图中出现了一个三角形ＡＢＣ，如图２．这意味着Ａ、Ｂ、Ｃ之间互相认识，同样证明了本题的结论．

像图１和图２那样由一些点和线所组成的图形在数学中称为图，专门研究图的性质的一门数学分支称为图论．图论是最近几十年才发展起来的，它依靠自己独特的思维方式解决了许多数……