说,由两个邻国,三个邻国、四个或五个邻国组成的一组“构形”是不可避免
的,每张地图至少含有这四种构形中的一个。
肯普提出的另一个概念是“可约”性。“可约”这个词的使用是来自肯普的论证。他
证明了只要五色地图中有一国具有四个邻国,就会有国数减少的五色地图。自
从引入“构形”,“可约”概念后,逐步发展了检查构形以决定是否可约的一些标准
方法,能够寻求可约构形的不可避免组,是证明“四色问题”的重要依据。但要
证明大的构形可约,需要检查大量的细节,这是相当复杂的。
年后,即 年,在牛津大学就读的年仅 岁的赫伍德以自己的精确计
算指出了肯普在证明上的漏洞。他指出肯普说没有极小五色地图能有一国具有
五个邻国的理由有破绽。不久,泰勒的证明也被人们否定了。人们发现他们实
际上证明了一个较弱的命题——五色 定理 。就是说对地图着色,用五种颜色就
够了。后来,越来越多的数学家虽然对此绞尽脑汁,但一无所获。于是,人们
开始认识到,这个貌似容易的题目,其实是一个可与费马猜想相媲美的难题。
进入 世纪以来,科学家们对四色猜想的证明基本上是按照肯普的想法在进
行。& 年,美国著名数学家、哈佛大学的伯克霍夫利用肯普的想法,结合
自己新的设想;证明了某些大的构形可约。后来美国数学家富兰克林于 &
年证明了 国以下的地图都可以用四色着色。 年,有人从 国推进到
& 国。! 年,有人又证明了 & 国以下的地图可以只用四种颜色着色;随
后又推进到了 国。看来这种推进仍然十分缓慢。
高速数字计算机的发明,促使更多数学家对“四色问题”的研究。从 &! 年就
开始研究四色猜想的海克,公开 宣称 四色猜想可用寻找可约图形的不可避免组
来证明。他的学生丢雷写了一个计算程序,海克不仅能用这程序产生的数据来
证明构形可约,而且描绘可约构形的方法是从改造地图成为数学上称为“对偶”
形着手。
他把每个国家的首都标出来,然后把相邻国家的首都用一条越过边界的铁路连
接起来,除首都,称为顶点-及铁路,称为弧或边-外,擦掉其他所有的线,剩下
的称为 原图 的对偶图。到了六十年代后期,海克引进一个类似于在电网络中移
动 电荷 的方法来求构形的不可避免组。在海克的研究中第一次以颇不成熟的形
式出现的“放电法”,这对以后关于不可避免组的研究是个关键,也是证明四色
定理的中心要素。
电子计算机问世以后,由于演算速度迅速提高,加之人机对话的出现,大大加
快了对四色猜想证明的进程。美国伊利诺大学哈肯在 " 年着手改进“放电过
程”,后与阿佩尔合作 编制 一个很好的程序。就在 "! 年 ! 月,他们在美国伊
利诺斯大学的两台不同的电子计算机上,用了 个小时,作了 亿判
断,终于完成了四色定理的证明,轰动了世界。