四色定理和库拉托夫斯基定理是离散数学中的两个基本结果，特别是在图论领域。这两个定理都从不同的角度阐述了平面图的性质。
在这篇文章中，我们将深入了解离散数学中的四色定理和库拉托夫斯基定理，它们的定义、示例以及它们之间的语义差异。
1852年，英国著名数学家兼逻辑学家奥古斯都·德·摩根的学生弗朗西斯·古特里提出了四色问题。他根据满足特定要求的地图定义了这个问题，例如地图不能有任何“空洞”，并且每个区域（例如国家或州）都是连通的，即不存在一个区域分布在两个或多个不相连的部分。
古特里断言，对于这样的地图，只需要不超过四种颜色来对地图进行着色，就能确保没有两个相邻部分的颜色相同。
如果地图M的区域被着色后相邻区域都不同，那么所需的颜色不会超过4种。
每个平面图都是4-可着色的（顶点着色），但当三角形是一个图或子图时，我们只需要3种颜色。
四色定理定义
> 四色定理指出，任何平面图（可以在平面上绘制且没有任何边交叉的图）都可以用最多四种颜色进行着色，使得没有两个相邻的顶点共享相同的颜色。
多年来，数学家们一直试图提出一种复杂的证明（关于着色定理），其思路类似于六色定理或五色定理，而使用暴力破解法几乎看起来像是在“破解”这个过程。
每个平面图都可以用四种不同的方式着色。
图中包含顶点和边。我们希望相邻的顶点/区域具有不同的颜色。
一个多世纪以来，该定理一直未被证明。1976年，肯尼斯·阿佩尔和沃尔夫冈·哈肯利用计算机提供了第一个被广泛接受的证明。
我们可以将地图转换为图，其中每个区域对应一个顶点，区域之间的每个边界对应一条边。问题最终归结为检查一个不可避免的构型集合。然后，确认该集合中的每个构型都是可约的。随后，使用计算机来检查每个构型的可约性。
如何着色？
选取任意地图，并将其划分为一组相连的区域：R1, R2 … Rn，它们具有连续的边界。
必须有一种方法可以为每个区域Ri分配集合 {R, G, B, Y} 中的颜色，使得如果两个区域Ri和Rj是“接触”的（即它们共享非零长度的边界），它们必须被分配不同的颜色。
示例 – 四色定理
- 下面展示了一张四色地图：
!image一张平面地图
如大家所见，每个接触其他区域的区域，其颜色都与被接触的区域不同，我们总共最多需要四种颜色来为这张地图着色——红色、绿色、蓝色 和黄色。
2. 下面展示了未着色地图 G 转换为着色地图的过程 –
!image地图 G
在这里大家可以看到，每个接触其他区域的区域，其颜色都与被接触的区域不同，我们总共最多需要四种颜色来为这张地图着色——红色、绿色、蓝色 和黄色。
3. 下面展示了未着色地图 H 转换为着色地图的过程 –
!image地图 H
在这里同样可以看到，每个接触其他区域的区域，其颜色都与被接触的区域不同，我们总共最多需要四种颜色来为这张地图着色——红色、绿色、蓝色 和黄色。
四色定理的应用
- 地图着色
- 频率分配
- 计算机图形学
- 益智游戏
- 网络设计
- 调度安排
- 图论
1930年，库拉托夫斯基确立了该定理，建立了平面性的充分必要条件。定理指出——
**“图 G 是非平面图当且仅当 G 包含一个子图，该子图是 K****3,3 或 K5 的细分。”**
库拉托夫斯基定理定义
> 库拉托夫斯基定理刻画了平面图的特征。它指出，一个图是平面图，当且仅当它不包含作为 K5（五个顶点的完全图）或 K3,3（完全二分图）细分的子图。