解法：阿佩尔–哈肯利用计算机验证可约性的放电法证明(1976年)

每张地图通过对偶给出一个平面图:在地图的每个区域内部放一个顶点,每当两个区域共用一条边界边就把对应顶点连一条边。地图可四染色当且仅当这个对偶图 $G$ 满足 $\chi(G) \le 4$,其中 $\chi(G)$ 是色数——正常顶点染色所需的最少颜色数。自环从不出现(没有区域与自身相邻),平行边也可合并为一条而不影响可染色性,故可取 $G$ 为简单平面图。

假设定理不成立,并取一个顶点数最少的反例 $G$:自然数的良序性保证只要反例存在,这样的 $G$ 就存在。极小性是整个论证的引擎——$G$ 的每个真子图或收缩图都更小,因而可四染色;此后每一步都通过先给更小的图染色、再在删去的部分上修补染色来利用这一点。这也解释了 $G$ 为什么既不能过疏也不能过硬:$K_5$ 非平面,所以 $G$ 不可能只是团式障碍;而平面性迫使 $G$ 含有下一步将要研究的低度结构。

这一策略——假设极小反例存在,再证明其必然出现的子结构全都可约——可追溯至 Kempe 1879年的尝试(其错误由 Heawood 在1890年指出),经 Birkhoff、再由 Heesch 发展;正是 Heesch 提出的不可避免集与可约性这两个概念,被 Appel 与 Haken 在其1977年发表于 Illinois Journal of Mathematics 的论文中贯彻到底。