四色定理
四色定理とは、いかなる地図も、隣接する領域が異なる色になるように塗るには4色あれば十分だという定理である。四色問題とも言う。
これは、グラフ理論において
- 平面グラフは4彩色可能である
四つの領域が互いに接しているような地図が存在するので、3色では不可能である。この問題は球面上のグラフで考えても同値である。問題を双対グラフに置き換えることによって、頂点を彩色することに帰着される。
歴史
地図を製作する際には国境線を接する国は別の色で塗らなくてはならないので、地図制作業者の間では何百年も昔から経験的に知られていた。18世紀後半になって数学者がその話を聞いて証明を試みたが、簡単そうに見える割に難しく、多くの数学者の挑戦をはねのけ続けてきた。そして、この定理は、グラフ理論における最も有名な未解決問題となったのであるが、1976年に Ken Appel と Wolfgang Haken によってコンピュータを駆使して証明された。
両人はまず、あらゆる平面グラフが約2000通りに分類できることを証明した。その後に、コンピュータを使ってその2000通りを総当たり式に調べ、確かに4色で彩色可能であることを確かめた。
その後、アルゴリズムは改良されたが、現在でもコンピュータを使用しない証明は得られていない。
5色で可能であることには、簡潔な証明がある。
トーラス（円環）上のグラフは、7色で彩色可能である。
（セルラーホンの基地局がこの理論で運用されている。CDMAになると関係なくなるのか）
