紙の上に鉛筆で閉曲線を描く．その際，自分自身と交差すること，また，交点では２個以上の弧が交わってもよいことにする．次に，閉曲線から得られた地図に色を塗るのだが，ある国を黒く塗りつぶし，国境線で隣り合う国はそのままにしておく．その結果は市松模様となるが，これは偶然ではない．

この２色定理の証明はあっけないほど簡単である．どの隣接する２面も同じ色でないように，白と黒の市松模様に塗ることができるためには，１の頂点で偶数の面が交わらなければならない（＝頂点の次数はすべて４以上の偶数）ことに気づきさえすればよい．

とはいえ，境界を接する２面（辺を共有する２面）が同じ色にならないように塗り分けるのに，２色しか必要としないのは驚くべきことである．地図が２色で塗り分けられるための必要十分条件を見いだす問題（＝２色問題）は地図塗り分け問題の特別な場合にあたるのである．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

いわゆる４色問題の由来は古く，１８５２年にさかのぼる．

「平面上の任意の地図を塗り分けるには４色が必要かつ十分であるか？」

は素人でも理解できる問題である．見た目には簡単には思えるが，実は容易に解ける問題ではなく，多くの間違った証明を生み出し，失敗と部分的解決が繰り返されてきた悪名高い問題である．

四色問題が肯定的に解決されたのは１９７６年のことで，アペルとハーケンはコンピュータ計算による網羅的な探求によりこの問題が正しいことを示した．５色で色分けできることはヒーウッドによって１００年以上も前から知られていたが，四色問題の証明は場合分けの数が膨大で，コンピュータによる解析に依存せざるを得なかったのである．

かくして４色問題は４色定理となった．これで，２次元では「どんな平面地図でも４色で塗り分けられる」ことが証明されたのだが，多くの数学者はこの証明においてコンピュータによる解析が本質的だと知ると落胆し，失望したと伝えられている．

その証明は１９９５年にロバートソン，サンダース，シーモア，トーマスの４人によって改良されてかなり簡単になったとはいえ，いまだ手計算で証明を完成させた人はいない．ともあれ，四色問題がグラフ理論の発展に対する推進力となったことは確かである．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝