四色定理
なお、境界線ではなく、点のみを共有する領域は隣り合っているものとはみなされず、互いに同色で塗ってもよい(飛び地の場合と同じく、この条件なしではやはり何色あっても足りなくなる。現実の地図では稀だが、有名なものでは米国に、1点に4州が接する「フォー・コーナーズ」という地点がある)。また平面だけでなく、球面の場合も同様である(平面の地図に、全周囲となる領域を加え、それを反対側の1点に集めるようにして球にすればよい。逆も同様)。しかし、ドーナツや「繋がったドーナツ」のような、穴がある形状の表面については同様とはいかない(これも後述)。
証明される前は四色問題と呼ばれることもあり、1975年に証明されたのだが、未証明の期間が長かったため現在でも四色問題と呼ばれることがある。
3つの境界線が1点に集まっている場所があるため、3色必要であることはただちに明らかである。続いて、ある領域の周囲にいくつかの領域がある場合(日本地図では長野県のような場合)を考える。周囲の領域の個数が偶数であれば3色で塗り分けできるが(長野県の場合はそうなる)、奇数個の領域で囲まれている場合は3色での塗り分けは不可能で、どうしても4色が必要である。そして、4色あればどんな場合でも塗り分け可能なのか? ということが問題である。
前述のように、グラフ理論により「平面グラフは4彩色可能である」という定理となる(証明もグラフ理論によってなされている)。参考例を図に示すが、まず、地図の境界線をグラフの辺、境界線が接続する点をグラフの頂点としたグラフを作る。その双対グラフにおける頂点の彩色が、元の地図の塗分けと同じ問題となる。
また、このような領域の塗り分けが有限の色数で必ず可能となるのは平面(二次元)以下の次元までであり、三次元以上では領域の取り方次第でいくらでも色数が必要な例が作れる。
グラフ理論的に言えば、この定理はループのない平面グラフに対して次のことを述べている。平面グラフ G {\displaystyle G} に対して、その彩色数は χ ( G ) ≤ 4 {\displaystyle \chi (G)\leq 4} である。
四色定理の直観的な記述 - 「平面を連続した領域に分割したとき、隣接する2つの領域が同じ色を持たないように、領域は最大でも4つの色を使って着色できる」 - を正しく解釈する必要がある。
これを「地図の塗り分け」とすると、例えば飛び地を所属地と常に同じ色にしなければならない、とした場合、何色あっても足りない、といった問題などがある。例えば、簡略化した地図を考えてみましょう:
この地図では、Aと書かれた二つの地域は同じ国に属している。もしこれらの領域に同じ色を与えたいならば、5つの色が必要になる。なぜなら、2つのA領域は一緒になって他の4つの領域に隣接し、それぞれの領域は他のすべての領域に隣接しているからである。なお別々の領域に同じ色を持たせることは、平面の外側にそれらをつなぐ'ハンドル'を追加することでモデル化できる。
このような構成によって、この問題はトーラス(種数1の曲面)上の地図の色付け問題と等価になる。
よってまず、日常的な直感から離れた表現で記述し直すと「境界線によって囲まれたいくつかの領域からなる平面図形があり、境界線の一部を共有する(隣り合った)領域は異なった色で塗らなければならない、としたとき、4色あれば十分である」となる。
グラフ理論でとらえると、
「平面グラフは4彩色可能である」
という定理になる(後述)。
リングの4つのカラーリングの数が多いので、これはコンピュータの支援を必要とする主要なステップである。
最後に、この手順で漸化できる構成の不可避集合を特定することが残る。このような集合を発見するために使われる主要な方法は、放電法である。放電法の根底にある直感的な考え方は、平面グラフを電気的なネットワークとして考えることである。最初に正負の「電荷」が頂点に分配され、合計が正になるようにする。
上の式を思い出してほしい:
∑ i = 1 D ( 6 − i ) v i = 12. {\displaystyle \sum _{i=1}^{D}(6-i)v_{i}=12.}
各頂点には6-deg(v)の初期電荷が割り当てられる。次に、ある頂点から隣接する頂点へ、規則に従って電荷を系統的に再分配することで電荷を「流す」(discharging procedure)。電荷は保存されるので、一部の頂点はまだ正の電荷を持っている。規則によって正電荷を持つ頂点の配置の可能性が制限されるので、そのような配置の可能性をすべて列挙すると、避けられない集合が得られる。
やむを得ない集合の中に還元可能でないものがある限り、(他の配置を導入しながら)それを取り除くように放電の手順を修正する。アペルとハーケンの最終的な排出手順は非常に複雑で、結果として得られる不可避的な構成集合の説明と合わせて400ページのボリュームを満たしたが、生成された構成が還元可能であることは機械的に確認することができた。不可避的コンフィギュレーションを記述した本そのものの検証は、数年にわたる査読によって行われた。
ここでは説明しないが、証明を完成させるために必要な技術的な詳細は、はめ込み 可約性'である。