『四色問題』

ロビン・ウィルソン 著／茂木健一郎 訳
新潮文庫
ISBN978-4-10-218461-5
その歴史を中心に四色問題について書かれた本。
一言でいえば悪くはない本で、悪くはないので、興味があるならば読んでみてもという本か。
ただし特別というほどのものはないと思う。
特別丁寧でもないし、特別分かりやすくもないし、しっかりと説明されているわけでもないし。
悪くはないというところ。
悪くはなく、こんなものといえばこんなもの。
それでよければ、という本だろう。

以下メモ。
・オイラーは任意の多面体について、
（面の数）+（頂点の数）＝（辺の数）＋2
という式が成り立つことを発見したが、多面体を平面に射影すれば、地図について、
（国の数）-（境界線の数）+（交点の数）＝2
（外部領域を含む）
という式が導かれる。
・多くの国と接している国は、その分境界線の数が増えてしまうので、この式が成り立つためには、隣国の少ない国が存在しなければならない。
・すべての交点で境界線の数が三本になっている三枝地図について考えると、ｘ個の隣国を持つ国c(x)の数について、オイラーの公式に境界線の数と交点の数を代入して、
4C(2)＋3C(3)+2C(4)+C(5)-C(7)-2C(8)-3C(9)-……＝12
という数え上げの公式が得られる。
（外部領域を含む。また、すべての地図は交点を変換することで三枝地図にできる）
・数え上げの公式の値が正の数になることから、すべての地図は、五個以下の隣国しか持たない国が少なくとも一つあることが分かる。
・この場合における五個以下の隣国しか持たない国のように、地図を描くときに避けることができない国の配置の集合を不可避集合と呼ぶ。
・四色予想が間違っていて、国を塗り分けるのに五色以上必要とする地図があったとき、そこに描かれている国の数には最小値が存在するはずである。
ある国数の地図が四色以下で塗り分けられないかもしれないが、それより少ない国数の地図は四色で塗り分けられる。
四色では塗り分けられない最小国数の地図に、隣国が二つの国があったとすると、この二辺国を潰した新しい地図は、仮定により四色で塗り分けられ、元に戻して二辺国を復元した地図は、二辺国は周囲には二色の色しかないから四色での塗り分けが可能で、四色では塗り分けられないとする最初の仮定に反している。
よって、四色では塗り分けられない最小国数の地図に隣国が二つの国は存在しない。
三辺国も同様にして最小国数の地図には含まれないことが証明できる。
二辺国や三辺国のように、最小国数の地図には含まれないような国の配置を可約配置と呼ぶ。四辺国も可約配置である。
・不可避集合に含まれる配置がすべて可約配置であることが示せれば、四色問題は証明されたことになる。
・この計算はコンピューターによって行われ、証明が完成した。