四色定理
四色定理の証明法は次の2段階に分けられる。
どのような平面グラフをとってきても、その集合に属するグラフのどれか一つが部分グラフとして含まれるグラフの集合を考える。このような性質をもつグラフの集合を不可避集合という。
不可避集合をうまく選ぶと、それに属するどのグラフも次の意味で可約にできる。すなわち、その部分グラフを含むグラフがあったとき、その部分グラフを除いたものが4色で塗り分けが可能ならば、グラフ全体も4色で塗り分けができる。
実際、もしも塗り分けに5色以上が必要な四色問題の反例となるグラフがあったとしたならば、その中で頂点の個数が最小のものを考える。すると、1.よりこのグラフは不可避集合に属する部分グラフを含む。2.により、この部分グラフを除いた、より頂点数の少ないグラフが既に四色問題の反例を与えることになる。しかし、それは最小の反例をとってきたという仮定に反する。
アッペルとハーケンはコンピュータによる実験を繰り返し、プログラムを何度も書き換えながら、可約なグラフから成る約2,000個のグラフからなる不可避集合を求めた。