五色定理

ウィキペディア

五色定理

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/08/02 08:42 UTC 版)

5色で塗り分けられた地図

グラフ理論における五色定理（ごしょくていり、英: five color theorem）とは、領域に分けられた平面、例えばある州を郡に分けた政治地図が与えられたとき、5種類以下の色を使って、隣接する領域が必ず別の色になっているように各領域を塗り分けられるという定理である。

五色定理はそれより強い四色定理の系であるが、証明ははるかに易しく、1879年にアルフレッド・ケンプ（ケンペとも）が四色定理（予想）を証明し損ねたときの論法に基づいて示せる。パーシー・ジョン・ヒーウッドは11年後にケンプの誤りを発見し、それを元に五色定理を証明した。

証明のアウトライン

まず、与えられた地図に単純な平面グラフ $G$

赤と青を交互に結んでゆくケンプ鎖。

グラフ $G'$ カテゴリ / コモンズ