“意外かもしれないが，地図製作に携わる人々は，四色問題を全然重視していない” 『四色問題 (新潮文庫) 』 Robin Wilson 著 茂木健一郎 訳 新潮社

四色問題 (新潮文庫)

Four Colors Suffice: How the Map Problem Was Solved: Revised Color Edition (Princeton Science Library)

誰でも（小学生でも）理解できる問題でありながら，２００年以上にわたって未解決であったことによって，また，その最終的な証明がコンピュータを使ってなされたという点において，注目を浴びていた４色問題．でも４色問題がどうアプローチされ，どのようにコンピュータの上に乗せられたのか．これは気になるところである．それをわかりやすく解説するともに，そして，歴史的な流れをみごとに語ってみせた良書である．
　こうした分野の翻訳，解説で著名な，竹内薫氏が，本書の解説で「名訳」であると言っているが，確かにたいへん良い訳である．単に日本語の質だけではなく，理解を助ける工夫がなされていることがよくわかる．
P.19

意外かもしれないが，地図製作に携わる人々は，四色問題を全然重視していない.

p49
ド・モルガンとハミルトンを引き合わせたのは，チャールズ・バベッジ（1830年頃）
p.86
オイラーの定理を証明したのは，ルジャンドル．
以下，本書のまとめ
１．四色問題：
　（１）定義
・すべての国を４色で塗り分けることができるか
・一点で交わる国は同色にしてよい
・飛び地はないものとする
　（２）
・考案者：フレデリック・ガスリー（1831-99）
・解決者：ヴォルフガング・ハーケン＆ケネス・アッペル

２．歴史
(ア) 1852年ド・モルガン（UCL）からウイリアム・ローワン・ハミルトン
宛の手紙

３．用語
　・国（領域），境界線，交点
　・三枝地図：すべての交点がちょうど３本の境界線を持つとき
　・n辺国：隣国がnヵ国ある国
　・最小犯例：ｎ色では塗り分けられない地図の中で，これより少ない国からなる地図はどれもｎ色で塗り分けられるもの
　・可約配置：最小反例には含まれないような国々の配置
　・不可避集合：その中の少なくとも一つがすべての地図に現れるような配置の集合
４．
　・地図についてのオイラーの公式：
（外部領域を含めるならば）
F（国の数）―E（境界線の和）＋V（交点の数）＝２

　・「隣国は五つだけ」定理：
どんな地図にも，五個以下の隣国しか持たない国が少なくとも一つある．
　　　証明：すべての国が６以上の隣国を持つとすると
E ≧ 6F/2 = 3F ⇔　F ≦ 1/3・E
E ≧ 3V/2 ⇔　V ≦ 2/3・E
F-E+V ≦ (1/3 - 1 + 2/3)E = 0
　　　　　　これはオイラーの公式と矛盾．背理法により証明された．

　・２，３，４辺国かなく，n個の５辺国があるとすると，
E ≧ (6(F-n) + 5n)/2 = (6F-n)/2 ⇔　F ≦ (2E+n)/6
E ≧ 3V/2 ⇔　V ≦ 2/3・E
2 = F-E+V ≦ (1/3 - 1 + 2/3)E +n/6 = n/6
∴n ≧ 12

　・数え上げ公式
n辺国の数をC_nとする．３枝地図について
2E = 2C_2 + 3C_3 + 4C_4 + ...
3V = 2C_2 + 3C_3 + 4C_4 + ...
F = C_2 + C_3 + C_4 + ...
2 = F-E+V = \Sum_{i=2}(1+ (-1/2+1/3)i)・C_i
= \Sum_{i=2}((6 - i)/6・C_i
12 = \Sum_{i=2}((6 - i)・C_i
= 4C_2 + 3C_3 + 2C_4 + C_5 - C_7 - 2C_8 - 3C_9 + ...

　・各国がr個の部分から構成されている場合，塗り分けには6r色が必要
十分性：ヘイウッド　必要性：ジャクソン＆リンゲル（1984）

　・トーラス上の地図に関するオイラーの公式：
F（国の数）―E（境界線の和）＋V（交点の数）＝０

　・トーラス上の地図に関する「隣国は六つだけ」定理：
トーラス上のどんな地図にも，六個以下の隣国しか持たない国が少なくとも一つある．
　　　　（同様に背理法により証明可能）

　・h個の穴があいたトーラス上の地図に関するオイラーの公式
F（国の数）―E（境界線の和）＋V（交点の数）＝２ - ２ｈ

　・ヘイウッド予想（1968年リンゲル＆ヤングスにより証明）
h個の穴があいたトーラスの表面には，塗り分けに
H(h) = [(7 + \sqrt{1 + 48h})/2] （[]はガウス記号）
　　　 色を必要とするような地図が存在する

【関連読書日誌】

• (URL)“オイラーの水晶のように透明なラテン語は、西洋の学者たちがこの言語で書くのをやめたときに西洋文明が失ったものに気づかせてくれる”　『素数に憑かれた人たち ~リーマン予想への挑戦~』　John Derbyshire,　松浦俊輔訳　日経BP社
• (URL)“もし読者が本書を読み始めたときよりもそれ以上の疑問を抱いて読み終えたならば，私は大変光栄である．”　『バナッハ=タルスキの逆説 豆と太陽は同じ大きさ? 』　レーナード・M・ワプナー　佐藤宏樹, 佐藤かおり訳　青土社

【読んだきっかけ】
【一緒に手に取る本】

四色問題―その誕生から解決まで (1978年) (ブルーバックス)

数学を変えた14の偉大な問題

これも数学だった!?: カーナビ、路線図、SNS (丸善ライブラリー)

Four Color

The Four-Color Theorem: History, Topological Foundations, and Idea of Proof