四色問題とは「四色あればどんな地図でも隣り合う国々が違う色になるように塗り分けることができるのか」という住学的な命題。
何年も数学者たちを悩ませてきた四色問題ですがコンピューターを使うことでようやく証明されました。
ちなみに、四色問題のような、今までに解かれてきた数学などの難問は、
「数学難問BEST100」小野田博一（PHP研究所）
「論理パラドクス 論証力を磨く９９問」
「論理パラドクス こころのワナ編 人はどう考えるかを考える７７問」
「論理パラドクス 勝ち残り編 議論力を鍛える８８問」
といった書籍で楽しく（？）学ぶことができます。
四色問題（四色定理）とは証明は？
四色問題（四色定理）は，すべての平面グラフが 4-彩色可能（隣接頂点が同色にならないように，4 色で頂点が彩色できる）というもの。
式や算数、数学では四色問題は解決されていません。
コンピュータでしらみ潰しにやっていったという証明方法です。
証明には背理法を使います。四色問題の否定を仮定して，矛盾を導きます。
仮定より，五色なければ塗り分けられない地図が存在します。そのような地図のうち，もっとも国数の少ない地図を「最小反例」と言います。塗り分けに四色で足りる地図は必ずある（例えば四つの国からなる地図）ので，最小反例は必ず存在します。少し工夫をすると，この最小反例に絶対に含まれないような国々の配置を見つけることができます。そのような配置を「可約配置」と呼びます。
一方，平面地図に出現しうる国々の配置にはさまざまなパターンのものがありますが，うまい工夫をすると，国々の配置を要素とする有限集合で，どんな地図でもこの集合の要素を少なくとも一つは含むような集合というのを作ることができます。このような集合を「不可避集合」といいます。不可避集合は無数にありますが，その中には可約配置だけを要素とするものがあるかもしれません。
もし，可約配置だけを要素とする不可避集合が存在すれば，四色定理が証明されたことになります。最小反例に決して含まれない「可約配置」がどんな地図にも不可避的に含まれるとすれば，最小反例は存在できないからです。
この「可約配置の不可避集合」を見つけるのがえらく大変で，1976年にアッペルとハーケンはコンピュータによる実験を繰り返し、プログラムを何度も書き換えながら、可約なグラフから成る約2,000個のグラフからなる不可避集合を求めた。
当時の大型汎用コンピュータIBM System/370を1,200時間以上使用したといわれている。
その後アルゴリズムは改良されたが、現在でもコンピュータを利用しないで済ませられる証明は得られていない。
複雑に思える問題に対して簡潔にまとまった比較的短い証明（解答）を、エレガントな証明（解答）と言うことがある。
四色定理に対するある種「力業による証明」は、これとは対極にあるものとして揶揄を込めて「エレファント（象）」な証明とも言われた。
5色による塗り分けが可能であることの証明が簡潔なものであるのとは対照的である。
四色問題（四色定理）はガリレオ容疑者Xの献身で石神も証明
映画「ガリレオ 容疑者Ｘの献身」の布石として帝都大学時代の湯川（福山雅治）と数学の天才・石神哲哉（堤真一）の間に交流が生まれるきっかけに、四色問題（四色定理）が取り上げられました。
物理の湯川と数学の石神専攻科目が違うからそんなに接点はなかったが、大学のキャンパスで石神さんが四色問題を解こうとしているのを湯川が見つけると、
「四色問題か。それはすでにコンピュータでは解かれている問題でないのか？」と質問しますが石神は「あの答えは美しくない」と答えています。
この「美しくない」に湯川はとても感心し、人間にあまり興味のない石神さんに湯川さんが関わって行き、二人が親しくなって行くという設定でした。
四色問題（四色定理）は映画のラスト、獄中でも石神が証明に取り組んでいるシーンがでてきます。
「隣同士が、同じ色になってはいけない」というセリフもみられますが、これは
「隣人の石神と靖子は恋愛で一緒になってはいけない」
「2人が同じく有罪になってはいけない」
の比喩になっていて、このストーリーとトリックの根底に流れる論理になっていると考察されています。
