五色定理：平面地図と平面グラフの5色彩色

前提と同値な定式化

通常の定式化では、各領域が連結していること、すなわち飛び地を持たないことが求められる。また、一点で接するだけの領域は隣接しているとは見なされず、同じ色にしてよい。こうした地図における条件は、平面グラフで用いられる標準的な隣接の定義に正確に対応する。同値な言い方として、この定理は、任意の平面グラフの頂点を高々5色で彩色でき、隣接する頂点には異なる色が与えられることを述べる。証明やアルゴリズムで最も多く用いられるのは、この頂点彩色の観点である。

証明の主要な考え方と構成的方法

五色定理の初等的な証明は、領域数または頂点数に関する帰納法で進められる。オイラーの公式から導かれる平面グラフの基本的な組合せ論的事実により、非自明な平面グラフには必ず次数が高々5の頂点が存在する。このような低次数の頂点を取り除き、帰納法の仮定によって残ったグラフを彩色した後、取り除いた頂点へ彩色を拡張することを試みる。

取り除いた頂点の次数が4以下ならば、未使用の色を必ず割り当てられる。唯一注意を要するのは次数が5の場合である。古典的な議論では、ケンペ連鎖という概念を導入する。これは、2色だけを用いる頂点から成る極大な連結路または連結成分である。適切なケンペ連鎖に沿って色を交換すれば、一つの色を空けて彩色を拡張できる。この交換を慎重に用いることで、常に成功する完全で有限な手順が得られ、5色で十分であることの正しい証明となる。

歴史的注記

この問題と関連する主張は、19世紀後半にさかのぼる。アルフレッド・ケンペによる初期の影響力ある議論は、五色証明に今も中心的な役割を果たす連鎖法を導入したが、より強い四色問題を証明しようとしたケンペの当初の試みには欠陥があった。パーシー・ジョン・ヒーウッドはその欠陥を分析し、この手法を応用して5色で十分であることの有効な証明を与えた。常に4色で十分であるという、より強い主張である四色定理は、はるかに高度な研究を必要とし、コンピュータ支援による場合分け解析の助けを得て20世紀後半になって初めて解決された。対比として四色定理を参照。

用途、アルゴリズム、および意義

五色定理は理論的にも教育的にも重要である。これは、帰納的かつ構成的な組合せ論的推論、ならびに平面位相とグラフ構造の相互作用を示す標準的な例となっている。また、単純で効率的な彩色アルゴリズムにもつながる。低次数の頂点を繰り返し除去し、必要に応じてケンペ連鎖の調整を適用することで、線形時間アルゴリズムは任意の平面グラフの5彩色を生成できる。このため、少数の固定された色の組で足りる応用では、5彩色は実用的である。

関連する区別と注目すべき事実

• 五色定理は四色定理より弱いが、人間が検証できる証明ははるかに簡明である。
• その証明は、平面グラフに次数が高々5の頂点が存在するという事実をはじめとする基本的な平面グラフの性質に依拠する。この事実はオイラーの公式と計数論法から従う。
• この定理に基づくアルゴリズムは、大規模なコンピュータによる場合分け検査を避けつつ構成的な彩色を与える。こうしたアルゴリズムは、地図の彩色、周波数割当て、その他平面性が現れる類似の問題で実用的である。

学習者向けの初等的な導入や証明については、多くの教科書がケンペ連鎖と帰納法による完全な五色証明を扱っている。地図としての解釈に関する理解しやすい概説や例は、オンライン資料や平面グラフ彩色の概説論文でも利用できる。そこでは、地図で述べられる地図上の隣接関係や、飛び地のような非連結の領域についても論じられている。平面グラフの彩色問題全般については、グラフ理論と組合せ論の標準的な文献および概説を参照するとよい。