1つの領域を国と呼ぶことにする。国と国の境目を国境と呼ぶことにする。
(1)
[補題] ある国から出発し、奇数回国境を渡って元の国に戻ってくる、ということはできないことを示す。

ある国から元の国に戻ってくる任意の道筋を考え、辿った道筋をCとする。
国境は一筆書きでかけるのだから、国境にはその一筆書きで定まる"向き"がついていると考えることができる。
このとき, Cがまたぐ国境のうち、「Cの中に入ってくる向きの国境」と「Cから出ていく向きの国境」の数は等しくなくてはならない。
(一筆書きの始点と終点は等しいから。)
よって、Cをたどるとき国境は必ず偶数回またぐ。(補題証明終)

そこで、次のように色分けする。

1つ国を指定し、A国とする。
A国から偶数回国境をまたいでたどり着ける国に赤、奇数回またがないとたどり着けない国に青を塗る。
すべての国は行き来できる(としてよい)から、これで塗ることはできた。あとはちゃんと塗り分けられているか。

赤と赤、青と青が接していることはないことを示す。
赤で塗られたB国と赤で塗られたC国が接しているとすると,
AからBへは偶数回国境をまたいで行けて, BからCへは1回, CからAへ偶数回またいで行けるから、
結局AからAに奇数回またいで行けることになり[補題]に矛盾してしまう。
青と青が接しているとしても同様に矛盾。

以上より、塗ることができた。