四色定理とは？
四色定理は、平面上に描かれたどんな地図も、境界を共有する 2 つの領域が同じ色にならないよう高々 4 色で塗れると述べる。1 点で接するだけの 2 領域は隣接とは見なさない。問題は単純に見えるが、証明には 1 世紀以上を要した。
領域 1、2、3、4 はそれぞれ複数の領域と境界を共有する。左と右の「4」の領域は境界を共有していないので同じ色を使える。この例では本当に 4 色が必要になる。
フランシス・ガスリーは 1852 年、イングランドの州地図を塗っているときにこの予想を立てた。4 色で常に十分に思えたが、証明できなかった。この問題は 124 年にわたり数学者を悩ませた。多くの「証明」が現れたが、すべて誤りであることが判明した。
四色定理は予想から証明まで 124 年かかった。1976 年の証明は、コンピュータで検証された最初の大定理だった。
1976 年、ケネス・アッペルとヴォルフガング・ハーケンは、あらゆる地図を 1,936 個の配置に還元し、その一つ一つをコンピュータで確認することで証明した。これはコンピュータ支援による最初の大定理となった。後により短い検証も与えられたが、四色定理はいまなお「機械が必要だった最初の大きな証明」として有名である。
外側の 5 領域（奇数個）は輪を 3 色で塗ることを強いる。5 周期は 2 色では塗れない。中心領域はその 3 色すべてに接するので、4 色目が必要になる。4 色が本当に必要な場合があることがわかる。
平面上のどんな地図も、境界を共有する領域が同色にならないよう高々 4 色で塗ることができる。1852 年にフランシス・ガスリーが予想し、1976 年にアッペルとハーケンが 1,936 個の配置をコンピュータで検証して証明した。これはコンピュータ支援によって証明された最初の大きな定理である。1997 年にはロバートソン、サンダース、シーモア、トーマスがより簡潔な検証を与えた。ときには 3 色では足りず、本当に 4 色が必要な地図が存在する。