四色定理

的四色定理声明任何地图(将平面划分成任意数量的区域)都可以使用不超过四种颜色上色，这样就不会有两个相邻的区域共享相同的颜色。用四种颜色绘制的世界地图四色定理特别引人注目，因为它是第一个由计算机证明的大定理。

有趣的是，尽管这个问题是由地图绘制引起的，但这个定理对这个领域并不是特别重要，因为历史上大多数地图都是用超过四种颜色绘制的(尽管只有四种是必要的)。此外，大多数实际地图只需要三种颜色。

虽然地图在非正式意义上可以被理解为可能相邻国家的集合，但每个国家都必须是这样连续/连接，大致意思是不需要离开这个国家就可以从一个国家的任何一点走到另一个国家的任何一点。实际上，情况并非如此:例如，密歇根州由两个互不相连的地区组成。

也有反例涉及有限面积和无限面积的映射周长，例如科赫雪花．当详述定理时，它们通常被忽略，因为它们不是非常有趣的例子。

一个更正式的陈述来自图论．如果每个国家用一个顶点表示，当且仅当两个顶点相邻时，两个顶点用一条边连接，则结果为a平面图．此外，还可以证明存在一个与任何平面图相对应的映射，因此定理可以理解为平面图上的一个结果。更具体地说，四色定理说明

的彩色数字的平面图最多是4。

的五个颜色定理显然比四色定理弱，但证明起来容易得多。事实上，它最早的证明是“偶然的”，是四色定理证明的一次有缺陷的尝试的结果。它的工作如下:

考虑一个平面图 $G$．可以证明 $G$必须有顶点 $v$共享最多5条边(*)。考虑到图 $G’$形成的删除 $v$所有的边 $v$从 $G$． $G’$仍然是平面的，所以它可以由感应那 $G’$可以用五种颜色着色。

如果 $v$最多连接四个顶点，结果立即为真，因为 $v$是简单地分配任何颜色不同于它的邻居，导致5色 $G$根据需要。因此，唯一重要的情况是在哪里 $v$与5个顶点相连 $V_1, v_2, v_3, v_4, v_5$(按顺时针的顺序)，这五个顶点有五种不同的颜色 $C_1, c_2, c_3, c_4, c_5$．

现在考虑所有顶点的颜色 $c₁$，所有顶点的颜色 $c_3$，以及它们之间所有的边。如果 $v_1$和 $v_3$在这个子图中是断开连接的，该组件包含 $v_1$可以用相反的方式着色(所有顶点都着色 $c₁$在这个组件中被重新着色 $c_3$反之亦然)，在这一点上 $v$可以用 $c₁$以结束证明。所以唯一重要的情况是 $v_1$和 $v_3$在这个子图中是连通的。

现在考虑所有顶点的颜色 $c₂$，所有顶点的颜色 $c_4$，以及它们之间所有的边。按照同样的逻辑，唯一重要的情况是 $v_2$和 $两者的$在这个子图中是连通的。但自 $v_1$被连接到 $v_3$， $v_2$无法连接到 $两者的$不破坏图形的平面性(回想一下 $V_1, v_2, v_3, v_4, v_5$是按顺时针顺序排列的 $G$）.因此，已经涵盖了所有的案例，结果由归纳法得出。 $_ \广场$

二十面体图的每个顶点都与另外五个顶点相连

人们很自然地会问，为什么这个证明对四色定理也不成立，因为似乎第五种颜色在这里起的作用很小。事实上，除了(*)语句之外，这个逻辑是完全有效的。特别是，这并不一定是真的 $G$最多与四条边相连的顶点;例如，对应于an的图二十面体它是平面的，每个顶点都与另外五个顶点相连。

与五色定理不同，四色定理很难证明。事实上，尽管这个问题在1852年就被严格地表述出来了，但直到1976年，一个正确的证明才首次发表。由于问题的性质，失败的方法异常多:例如，肯普在1879年给出了一个证明，在被驳倒之前持续了11年;尽管如此，它还是引出了上述五色定理的证明。

使用的最终证明最小化:证明了任何反例都必须包含作为a的图集合中的一个子图但如果这些子图是反例的一部分，就会有一个更小的反例存在。这证明了不存在最小的反例，所以根本不存在反例。

更正式,

• 一个不可避免的设置是一组图，使得任何最小的四色定理反例都必须包含至少一个作为子图的图。
• 一个可还原的配置是一个图，具有以下性质:任何包含可约构形的映射都可以被缩减为一个更小的映射，满足小的映射可以用4种颜色上色，原映射也可以用4种颜色上色的条件。

如果能找到一个不可避免的可约构形集合，那么就足以证明该集合中的每一个图都是四色的。这正是1976年证明的结果，证明存在一组1936年大小的不可避免的可约构形。在超级计算机上检查这些配置需要1000多个小时。

四色定理可以推广到无限的图每个有限子图都是平面的，这是De Bruijn-Erdos定理:

无限图 $G$可以用 $k$色的当且仅当 $G$可以用 $k$颜色。 $_ \广场$

这一结果在实际工程中具有重要的应用价值平面的色数这个问题问的是，需要多少种颜色才能确保平面上的每个点与距离它单位距离的任何点不共享一种颜色。特别地，这一结果表明，平面的色数在4到7之间。

它也值得考虑着色划分的表面，而不是平面。因为平面可以映射到球体上，所以四色定理也适用于球体，也就是说球体上的任何地图最多可以被涂上四种颜色。然而，陌生的表面需要更多的颜色:例如，分割克莱因瓶和莫比乌斯带两者都需要6种颜色。

最后，这些结果都不能扩展到三个维度:设计一个每一对都是的例子相对容易 $n$柔性杆是相邻的，所以它们需要 $n$任意整数的颜色 $n$．因此，在高维中没有类似于四色定理的东西。

• 图论