文系の方への証明。

１色の領域で表した「国」の中の適当な場所に、必ず１点だけ「首都」があります。
「国」と「国」が隣接するときには、必ず両国の首都がその国境を通過する「幹線道路」で繋がっています。
すると、隣接するＡ国とＢ国の首都を結ぶ幹線道路と、Ｃ国とＤ国の首都を結ぶ幹線道路は、「絶対に交差しません。」
だって、Ａ−Ｂの幹線道路はＡとＢの国土のみ通っているので、Ｃ−Ｄの幹線道路が交差するなら、その交差点はＡＢＣＤいずれにも属することとなり、「幹線道路」の定義に反するからです。

以上を前提に、隣り合う国は別の色で分ける場合に、色分けに必要な色の数、というのは、つまり、
幹線道路で全ての首都が相互に繋がることができる国の数、ということになります。

で、紙に鉛筆で、適当に点（首都）を２個を描いて、その間を結ぶ線（幹線道路）も描いてください。
次に点を増やして３点にしてみましょう。三角形のように描くと、頂点が「首都」で、辺が「幹線道路」のようになりますが、３点は相互に繋がってますね。ちなみに、線は絶対に交差しないように描かなければなりません。
次に４点。これも、相互につながる線を描けますね。
で、問題は次です。５点目。これは、どの領域に書いても、必ず「相互につなぎようのない２点」が生じます。つまり、その２点は同じ色を使えるわけです。
同様に、６点以上増やしてもトートロジーで、相互につながる点は４個以上は書けません。
ということは・・・。

つまり、まあ、その、そういうことです。