解法: 計算機検証による可約性を伴うAppel–Hakenの放電法証明(1976年)

ステップ 1/8: 地図の彩色を平面グラフの彩色に帰着させ、背理法を用いる

ざっくり言うと

地図の各国の中に一つずつ点を描き、二つの国が国境を接するたびにその二点を線で結ぶ。すると、「どんな地図も隣国どうしが異なる色になるよう $4$ 色だけで塗れるか」という地図彩色の問いは、「このグラフの点を、線で結ばれた二点が決して同じ色にならないように塗れるか」という問いに変わる。

どんな地図も $5$ 色目を必要としないことを証明するために、数学者たちは逆を想定する:もしどこかに本当に $5$ 色を必要とする地図があるとしたら、そのような厄介な地図すべての中から最小のものを一つ選ぶ。その仮定が矛盾を導けば、そのような地図はそもそも存在し得ない——これは極小反例と呼ばれる古典的な証明戦略である。

\chi(G) \le 4 \ \text{for every planar graph } G

詳しい解説

各地図を平面グラフ $G$ (各領域を頂点、隣接する領域間に辺)として表す。証明すべき主張は $\chi(G) \le 4$ となる。ここで $\chi(G)$ は彩色数、すなわちどの辺も同色の二頂点を結ばないようにするために必要な最小の色数である。

Alfred Kempe(1879年)が先駆けとなり、Percy Heawood(1890年)が修正した戦略にならい、反例—— $5$ 色を必要とするある平面グラフ——が存在すると仮定して矛盾を導く。すべての反例の中から極小な反例 $G$ (頂点数が最小で $\chi(G) \ge 5$ を満たす平面グラフ)を一つ選ぶ。このとき $G$ の真部分グラフはすべてより小さいので $\chi \le 4$ を満たす。

この極小反例こそが、以降のすべてのステップで研究される対象である。そのような $G$ が実際には存在し得ないことが示せれば、四色定理は直ちに従う。

このステップの用語

彩色数 $\chi(G)$: グラフ $G$ の頂点を、同色の二頂点を結ぶ辺が一つもないように塗るために必要な最小の色数。
極小反例: 主張された定理に反するすべての対象(ここでは平面グラフ)のうち最小のもの。それがさらに小さい反例を含まなければならないことを示して矛盾を導く際に用いる。

このステップで使う知識

平面グラフグラフ彩色と四色定理