关于五色定理

关于五色定理

五色定理是图论中的一个结论：将一个平面分成若干区域，给这些区域染色，且保证任意相邻区域没有相同颜色，那么所需颜色不超过五种。
五色定理是比四色定理弱的定理，但是比四色定理更容易证明。1879年，阿尔弗雷德·布雷·肯普给出了四色定理的一个证明，当时为人所接受，但11年后，珀西·约翰·希伍德却发现了肯普的证明中存在错误，他把肯普的证明加以修改，得到了五色定理。
1879 年英国律师出身的数学家肯普在美国数学杂志上发
图1 普肯的证明
表一篇论文。他声称自己已经解决了四色问题。并因其对数学的贡献最终被封为爵士。他用归谬法证明“四色猜想”，提出了“不可避免集”的构形和构形的可约性。他用肯普链的方法证明，如图1，如果一个顶点 V与 5 个其他用四种颜色着色的点邻接，那么总能多出诸颜色之一来给 V着色，他用了邻接点交错着色的道路（肯普链），交换这些道路上的颜色，以便空出一种颜色给 V。
1890 年英国著名数学家希伍德发表了一篇论文。这篇论文震动了数学界。他举出了“有名反例”，如图 2。在肯普看上去解决了这个问题之后 10 年，希伍德用这个“反例”揭示肯普证明四色问题有重大缺陷，并证明反
图2
例是 5- 色的，如图2 到图 7。从而希伍德指出：“如果‘四’换成‘五’这个猜想就对了”。他否定了肯普“四色猜想”的证明。肯普失败了。同时希伍德证明建立了“五色定理”。
从此人们把图分为可约图和不可约图，可约图是 4- 色的，不可约图是 5- 色的，即不可约图有 3 个特征：（1）图是最大平面图；（2）图是 5-色的顶点着色法；（3）图是临界的收缩。希伍德的“反例”就是不可约图。希伍德的反例和他的“五色定理”的存在，使人们产生了误解中的“四色猜想”，即只证可约图（平面地图），而不证不可约图（球面地图），一直流传至今。谁也不敢反对它，把它视为真理。这样一来的100 多年，彻底解决“四色猜想”的研究，就被希伍德的“反例”和他的“五色定理”占了统治地位。尽管世界上一些数学家仍然孜孜不倦地致力寻求彻底解决“四色猜想”的研究，就是 1976 年和 1996 年美国多位学者验证的“四色猜想”只有可约图，而没有不可约图。所以都超不出希伍德的“反例”和“五色定理”的范围