四色定理
どんな地図も、隣り合う国が同じ色にならないように 4 色で塗り分けられる。自分で塗るか自動で塗り、3 色では足りない地図も確かめる。
解説
考え方
四色定理は「平面上のどんな地図も、となり合う領域が同じ色にならないように塗り分けるには 4 色あれば十分」という定理。ただし、点だけで接している領域はとなり合っているとはみなさない。また、飛び地を本国と同じ色で塗らなければならないとすると、この定理は成り立たなくなる。
歴史
この問題は 1852 年、フランシス・ガスリーが地図の塗り分けから気づいたことに始まる。1879 年にケンプが証明を発表したが、1890 年にヒーウッドが誤りを指摘し、同時に「5 色なら十分」という五色定理を証明した。1976 年、アッペルとハーケンがコンピュータを使い、膨大な数の配置を一つずつ調べることで四色定理を証明した。
補足
人の手では確かめきれない証明だったため、当初は疑問視する声もあった。1996 年にはロバートソンらが調べる配置を 633 個に減らした新しい証明を示し、その後ゴンティエらが証明支援系 Coq で証明全体を検証した。現在でもコンピュータを使わない証明は見つかっていない。