四色定理

概要

「平面上のどんな複雑な地図でも、隣り合う領域が同じ色にならないように塗り分けるには、4色あれば十分である」という数学の定理。 100年以上証明されなかった難問（四色問題）。

コンピュータによる証明

1976年、アッペルとハーケンが、地図のパターンを約2000通りに分類し、当時のスーパーコンピュータを1200時間回してしらみ潰しに検証させることで証明した。 これは数学史上初めて「人間が手計算で検証不可能な証明」が認められた例となり、「それはもっとエレガントな論理で解くべきだ（美しくない）」と批判も浴びた。

例外

• 飛び地: アメリカのアラスカ州のように、領土が離れている場合は、同じ色で塗らなければならないため、5色以上必要な場合がある（定理の条件に含まれない）。
• ドーナツ型（トーラス）: ドーナツの表面に地図を描く場合は、7色必要になる。