狄拉克定理的新证明

对于一个给定的连通图,是否存在哈密尔顿(Hami lton)回路。这是图论中至今尚未解决的一个著名难题。1952年,欧洲数学家狄拉克(Dirac)建立了下面的定理,简单明瞭地给出了哈密顿回路存在的充分条件,这是图论史上的一项重大成果。 定理(Dirac):具有n(n≥3)个顶点的简单图,如果每个顶点V的度d(V)≥n/2,则一定存在一条哈密尔顿回路。 纽曼(Newman)与波塞(Posa)曾分别于1958年与1960年对狄拉克定理作出“光彩夺目”的证明(1)。现在所见的图论著作(2)中又用反证法给予证明。在本文中,笔者分别用逐步调整法与数学归纳法给出两种新证法,以供同行研究参考。 为了避免使用图论术语,我们不妨将狄拉克定理改述为与之等价的命题: 现有n(n≥3)个人,每个人的朋友至少有n/2个,则这n个人可以围坐一圈。