四色定理
的四色定理规定任何地图——将平面划分为任意数量的区域——可以使用不超过四种颜色进行着色,且相邻的两个区域不能使用相同的颜色。
四色定理是第一个被计算机证明的主要定理。有趣的是,尽管这个问题是由地图制作引起的,但这个定理对这个领域并不是特别重要,因为历史上大多数地图都是用超过四种颜色绘制的(尽管只有四种是必要的)。此外,大多数实际出现的地图只需要三种颜色。
正式声明
五色定理的证明
的五个颜色定理显然比四色定理弱,但证明起来要容易得多。事实上,它最早的证明是“偶然”发生的,是证明四色定理的一次有缺陷的尝试的结果。它的步骤如下:
考虑一个平面图 .这可以证明 必须有一个顶点 最多被5条边共享(*)。考虑到图 形成的删除 所有的边 从 . 仍然是平面的,所以可以由感应那 可以用五种颜色上色。
如果 被连接到最多四个顶点,结果立即为真 简单地分配了与相邻颜色不同的任何颜色,导致了5种颜色的 根据需要。因此,唯一重要的情况是在哪里 连接到五个顶点 (按顺时针顺序),这五个顶点用五种不同的颜色着色 .
现在考虑所有的顶点 ,所有的顶点都用 ,以及它们之间的所有边。如果 而且 在这个子图中是断开的,包含 可以以相反的方式着色(所有顶点着色 在此组件中被重新着色 ,反之亦然),此时 可以用 来结束证明。因此,唯一重要的情况发生在 而且 在这个子图中是连通的。
现在考虑所有的顶点 ,所有的顶点都用 ,以及它们之间的所有边。根据同样的逻辑,唯一重要的情况发生在 而且 在这个子图中是连通的。但自 被连接到 , 无法连接到 不破坏图形的平面性(回想一下 是按顺时针顺序列出的给定方向 ).因此,已经涵盖了所有的案例,结果由归纳法得出。
人们很自然地会问,为什么这个证明对四色定理也不成立,因为第五种颜色在这里起的作用似乎很小。事实上,除了(*)语句之外,逻辑是完全有效的。特别是,它不一定是真的 有一个顶点与最多四条边相连;例如,对应于an的图二十面体是平面的,并且每个顶点都与其他五个顶点相连。
四色定理证明方法
与五色定理不同,四色定理很难证明。事实上,尽管这个问题在1852年就被严格地表述出来了,但直到1976年才有了一个正确的证明。由于问题的性质,失败的方法异常多:例如,肯普在1879年给出了一个证明,在被驳斥之前坚持了11年;尽管如此,它还是导致了上述五种颜色定理的证明。
使用的最终证明最小化:任何反例都必须包含一组图中的一个作为a子图但如果这些子图中的任何一个是反例的一部分,那么就会存在一个更小的反例。这证明了这个结果,不可能有最小的反例,所以根本不可能有任何反例。
更正式,
- 一个不可避免的设置是这样一组图:四色定理的任何最小反例都必须包含其中至少一个图作为子图。
- 一个可还原的配置是一个具有以下属性的图:任何包含可约构型的映射都可以简化为一个较小的映射,满足如果较小的映射可以用4种颜色着色,则原映射也可以用4种颜色着色的条件。
如果一个不可避免的可约构型集可以被找到,那么它就足以证明这个集合中的每个图形都可以是四色的。这正是1976年证明的结果,表明存在一组不可避免的尺寸为1936的可约构型。在一台超级计算机上检查这些配置花费了1000多个小时。
进一步的结果
四色定理可以推广到无限的图每个有限子图都是平面的,这是De Bruijn-Erdos定理:
无限图 可以用 颜色当且仅当有限子图 可以用 颜色。
这一结果对我国的经济发展具有重要的应用价值平面的色数这个问题问的是需要多少种颜色才能保证平面上的每个点与距离它一个单位距离的任何点不共用一种颜色。特别地,这个结果表明平面的色数在4到7之间。
也值得考虑在平面以外的表面上着色。由于平面可以映射到球体,四色定理也适用于球体,本质上说,球体上的任何地图最多可以用四种颜色着色。然而,更奇怪的表面需要更多的颜色:例如,划分克莱因瓶而且莫比乌斯带都需要6种颜色。
最后,这些结果都不能扩展到三维空间:相对容易想出一个例子,其中每一对 柔性杆是相邻的,所以它们需要 任意整数的颜色 .因此,在高维空间中没有类似的四色定理。