四色定理

数学における四色定理、あるいは四色地図定理は、地図上の領域を色分けするのに4色以上は必要ないため、隣接する2つの領域が同じ色になることはないというものである。隣接とは、2つの領域が長さがゼロでない共通境界を共有することを意味する（つまり、3つ以上の領域が接する単なる角ではない）。^{[1]これは、}コンピュータを使用して証明された最初の主要な定理であった。当初、この証明は、コンピュータ支援による証明を人間が手作業で確認することは不可能であったため、すべての数学者に受け入れられたわけではなかった。^[2]この証明はそれ以来広く受け入れられているが、いくつかの疑問は残っている。^[3]

この定理は五色定理のより強いバージョンであり、はるかに単純な議論で証明できます。弱い五色定理は1800年代にすでに証明されていましたが、四色定理は1976年にケネス・アペルとヴォルフガング・ハーケンによって証明されるまで証明されませんでした。これは、それ以前の数十年間に多くの誤った証明と誤った反例があった後のことでした。

アペル・ハーケンの証明は、非常に多くの簡約可能な構成を分析することによって進められます。これは 1997 年にロバートソン、サンダース、シーモア、トーマスによって改良され、そのような構成の数を 633 にまで減らすことに成功しました。それでも、非常に長いケース分析です。2005 年に、この定理はジョルジュ・ゴンティエによって汎用定理証明ソフトウェアを使用して検証されました。

グラフ理論的に言えば、定理は、ループのない 平面グラフ の場合、その彩色数は であると述べています。 ${\displaystyle G}$${\displaystyle \chi (G)\leq 4}$

4 色定理の直感的な記述、「平面を連続した領域に分割する場合、隣接する 2 つの領域が同じ色にならないように、最大​​ 4 色を使用して領域を色付けできる」は、正しく解釈される必要があります。

まず、領域が隣接しているのは、境界セグメントを共有している場合です。孤立した境界ポイントのみを共有している 2 つの領域は隣接しているとは見なされません。(そうでない場合、円グラフの形状のマップでは、共通の角で互いに「隣接」する領域が任意の数だけ存在し、その結果、任意の数の色が必要になります。) 次に、面積は有限だが周囲が無限に長いなどの奇妙な領域は許可されません。そのような領域を含むマップでは、4 色以上が必要になる場合があります。^[4]（安全のため、境界が有限個の直線セグメントで構成される領域に限定することができます。領域が飛び地を持つこと、つまり、1つ以上の他の領域を完全に囲むことは許可されています。）「連続した領域」（技術的には、平面の連結された開部分集合）の 概念は、通常の地図上の「国」の概念と同じではないことに注意してください。国は連続している必要はありません（飛び地を持つことはできます。たとえば、アンゴラの一部であるカビンダ州、アゼルバイジャンの一部であるナヒチェヴァン、ロシアの一部であるカリーニングラード、海外領土を含むフランス、および米国の一部であるアラスカは連続していません）。国の領土全体を同じ色にする必要がある場合、4色では必ずしも十分ではありません。たとえば、簡略化された地図を考えてみましょう。

この地図では、ラベルAの付いた 2 つの地域は同じ国に属しています。これらの地域に同じ色を割り当てるには、5 つの色が必要になります。2 つのA地域は合わせて 4 つの他の地域に隣接しており、各地域は他のすべての地域に隣接しているからです。

定理をより簡単に述べるには、グラフ理論を使う。地図の領域の集合は、各領域に頂点を持ち、境界セグメントを共有する領域の各ペアに辺を持つ無向グラフとして、より抽象的に表現できる。このグラフは平面である。つまり、各頂点を対応する領域内の任意の位置に配置し、辺を、ある領域の頂点から共有境界セグメントを横切って隣接する領域の頂点に至る交差のない曲線として描くことで、平面に交差なしで描くことができる。逆に、この方法で地図から任意の平面グラフを形成することができる。グラフ理論の用語では、4色定理とは、すべての平面グラフの頂点は最大4色で色付けでき、隣接する2つの頂点が同じ色になることはない、つまり、すべての平面グラフは4色で色付け可能である、ということを述べている。^[5]

知られている限りでは、^[6]この予想が最初に提案されたのは 1852 年 10 月 23 日で、^[7]フランシス・ガスリーがイングランドの地図に色を塗ろうとした際に、必要な色は 4 色だけであることに気づいたときです。当時、ガスリーの弟のフレデリックは、ユニバーシティ・カレッジ・ロンドンでオーガスタス・ド・モルガン(フランシスの元指導教官)の学生でした。フランシスはフレデリックにこの件について問い合わせ、フレデリックはこれをド・モルガンに持ち込みました (フランシス・ガスリーは 1852 年に卒業し、後に南アフリカで数学の教授になりました)。ド・モルガンによると:

私の学生 [ガスリー] が今日、私が事実だと知らなかった、そして今も知らない事実の理由を教えてくれるよう私に頼んできました。彼によると、図形がどんな形であれ分割され、区画が異なった色に塗られ、共通の境界線の一部を持つ図形が異なった色に塗られる場合、4 色は必要かもしれないがそれ以上は必要ではない、とのことです。以下は 4 色が必要な彼の例です。5 色以上が必要であることは考えられないのでしょうか... ^[8]

おそらく二人のガスリーの一人である「FG」は、1854年にアテナエウム誌^{でこの問題を発表し、 [9]}ド・モルガンは1860年に同じ雑誌で再びこの問題を提起した。 ^[10]アーサー・ケイリー（1879年）による別の初期の文献 では、この予想はド・モルガンによるものとされている。

定理を証明する試みは初期に何度か行われましたが失敗しました。ド・モルガンは、定理は 4 つの領域に関する単純な事実から導かれると信じていましたが、その事実がより基本的な事実から導き出されるとは信じていませんでした。

これは次のようにして生じる。4 つの郡があり、それぞれの郡が他の 3 つの郡と共通の境界線を持っている場合を除いて、近隣に 4 つの色を使用する必要はない。4 つの地域では、そのうちの 1 つ以上が他の地域に囲まれていない限り、そのようなことは起こらない。そして、囲まれた郡に使用される色は、このように自由に使用できる。さて、4 つの地域が囲まれていない限り、それぞれが他の 3 つの地域と共通の境界線を持つことはできないというこの原理は、より明白でより基本的なもので証明できるものではないと私たちは確信している。それは、公理として成り立つに違いない。^[10]

1879年にアルフレッド・ケンプが提案した証明は広く称賛された。^{[11]もう1つは1880年に}ピーター・ガスリー・テイトが提案した。 1890年にケンプの証明がパーシー・ヒーウッドによって誤りであることが示され、1891年にはテイトの証明がジュリアス・ピーターセンによって誤りであることが示され、それぞれの誤った証明は11年間にわたって異論なく残された。^[12]

1890年、ヒーウッドはケンプの証明の欠陥を暴露しただけでなく、五色定理を証明し、四色予想を任意の種数の曲面に一般化した。^[13]

テイトは1880年に、四色定理はある種のグラフ（現代の用語ではスナークと呼ばれる）は非平面でなければならないという主張と同等であることを示した。^[14]

1943年、ヒューゴ・ハドヴィガーはハドヴィガー予想^[15]を提唱した。これは4色問題の広範囲にわたる一般化であるが、現在でも未解決のままである。

1960年代から1970年代にかけて、ドイツの数学者ハインリッヒ・ヘーシュは、証明を探すためにコンピュータを使用する方法を開発した。彼は定理を証明するために放電法を初めて使用した人物であり、これはその後のアペル・ハーケンの証明の不可避性の部分で重要になることが判明した。彼はまた、還元可能性の概念を拡張し、ケン・デュレとともにそのコンピュータテストを開発した。残念ながら、この重要な時期に、彼は研究を続けるために必要なスーパーコンピュータの時間を確保することができなかった。^[16]

他の人々も彼の手法を採用し、その中にはコンピュータ支援アプローチも含まれていた。他の数学者チームが証明を完成させるために競い合っている中、イリノイ大学のケネス・アペルとヴォルフガング・ハーケンは1976年6月21日に^[17]定理を証明したと発表した。彼らはジョン・A・コッホの支援を受けてアルゴリズムの作業を行った^{[18] 。}

もし4色予想が偽であれば、5色を必要とする最小の領域数を持つ地図が少なくとも1つは存在することになる。証明では、2つの技術的概念を用いて、そのような最小の反例は存在しないことを示した。^[19]

1. 不可避集合とは、最小の 4 色でない三角形分割となるためのいくつかの必要条件(最小次数が 5 であるなど) を満たすすべてのマップが、この集合から少なくとも 1 つの構成を持たなければならないような構成の集合です。
2. 縮小可能な構成とは、最小の反例には現れない国の配置です。マップに縮小可能な構成が含まれている場合、マップはより小さなマップに縮小できます。この小さなマップには、4 色で色付けできる場合は元のマップにも適用されるという条件があります。つまり、元のマップを 4 色で色付けできない場合は、より小さなマップも 4 色で色付けできないため、元のマップは最小ではありません。

アペルとハーケンは、簡約構成の特性に基づく数学的規則と手順を使用して、不可避な簡約構成の集合を発見し、4色予想に対する最小の反例は存在しないことを証明した。彼らの証明は、無限の可能性のある写像を1,834の簡約構成（後に1,482に削減）に削減したが、これはコンピュータで1つずつ確認する必要があり、1000時間以上を要した。この作業の簡約性の部分は、異なるプログラムとコンピュータで独立して二重チェックされた。しかし、証明の不可避性の部分は、ハーケンの娘ドロテア・ブロスタインの助けを借りて手作業で確認する必要があった400ページを超えるマイクロフィルムで検証された。^[20]

アペルとハーケンの発表は世界中のニュースメディアで広く報道され、^[21]イリノイ大学数学科は「4色で十分」と書かれた消印を使用した。^[22]同時に、証明の異例な性質（これは大規模なコンピュータ支援によって証明された最初の主要な定理であった）と人間が検証できる部分の複雑さがかなりの論争を引き起こした。^[23]

1980年代初頭、アペル＝ハーケンの証明に欠陥があるという噂が広まった。アーヘン工科大学のウルリッヒ・シュミットは、1981年に出版された修士論文のためにアペルとハーケンの証明を調べた。 ^{[24]彼は不可避性の部分の約40％をチェックし、排出手順に重大な誤りを発見した（アペル＆ハーケン1989）。1986年、アペルとハーケンは、}数学インテリジェンサーの編集者から、彼らの証明の欠陥の噂に対処する記事を書くように依頼された。彼らは、噂は「[シュミットの]結果の誤解」によるものだと答え、詳細な記事を書いた。^[24]彼らの最高傑作であるEvery Planar Map is Four-Colorableは、完全で詳細な証明（400ページを超えるマイクロフィルムの付録付き）であると主張した本で、1989年に出版された。この論文では、シュミットが発見した誤りと、他の人が発見したいくつかの誤りを説明・修正した。^[20]

定理が証明されて以来、新しいアプローチによって、4色マップの証明がより短くなり、より効率的なアルゴリズムが生まれました。1996年に、Neil Robertson、Daniel P. Sanders、Paul Seymour、Robin Thomasは^、 AppelとHakenの証明に基づく4次時間アルゴリズムを改良した2次時間アルゴリズム（O ( n2 )時間のみ必要、nは頂点の数）を作成しました。 ^[25]同じアイデアに基づく新しい証明は、AppelとHakenの証明に似ていますが、問題の複雑さを軽減し、633の簡約可能な構成のみを確認する必要があるため、より効率的です。この新しい証明の不可避性と簡約性の部分はどちらもコンピューターで実行する必要があり、手作業で確認するのは非現実的です。^[26] 2001年に、同じ著者はスナーク予想を証明することによって、別の証明を発表しました。^[27]ただし、この証明は未発表のままです。

2005年、ベンジャミン・ヴェルナーとジョルジュ・ゴンティエは、Coq証明支援システム内で定理の証明を形式化しました。これにより、特定のケースを検証するために使用されるさまざまなコンピュータプログラムを信頼する必要がなくなり、Coqカーネルを信頼するだけで済みました。^[28]

以下の議論は、すべての平面地図は 4 色に色分け可能(Appel & Haken 1989)の序文に基づく要約です。ケンペの 4 色定理の当初の証明は、欠陥はあるものの、後に証明に使用された基本的なツールの一部を提供しました。ここでの説明は、上記の現代のグラフ理論の定式化に基づいて言い換えられています。

Kempe の議論は次のようになります。まず、グラフによって区切られた平面領域が三角形化されていない場合 (つまり、境界内に 3 つのエッジが正確にない場合)、新しい頂点を追加せずにエッジを追加して、境界のない外側の領域を含むすべての領域を三角形にすることができます。この三角形化されたグラフが 4 色以下で色付け可能であれば、エッジを削除しても同じ色付けが有効であるため、元のグラフも 4 色以下で色付け可能です。したがって、すべての平面グラフに対して証明するには、三角形化されたグラフの 4 色定理を証明すれば十分であり、一般性を失うことなくグラフが三角形化されていると仮定します。

v、e、f を頂点、辺、領域（面）の数とします。各領域は三角形で、各辺は 2 つの領域で共有されるため、 2 e = 3 fとなります。これをオイラーの公式v − e + f = 2と組み合わせると、 6 v − 2 e = 12 であることがわかります。ここで、頂点の次数とは、その頂点に接する辺の数です。v n_を次数nの頂点の数、D を任意の頂点の最大次数とすると、

${\displaystyle 6v-2e=6\sum _{i=1}^{D}v_{i}-\sum _{i=1}^{D}iv_{i}=\sum _{i=1}^{D}(6-i)v_{i}=12.}$

しかし、12 > 0 であり、すべてのi ≥ 6 に対して 6 − i ≤ 0 であるため、次数 5 以下の頂点が少なくとも 1 つ存在することがわかります。

5 色を必要とするグラフがある場合、任意の頂点を削除することで 4 色に着色できるような最小のグラフが存在します。このグラフをGと呼びます。すると、G は次数 3 以下の頂点を持つことができません。これは、d ( v ) ≤ 3 の場合、 Gからv を削除して小さい方のグラフを 4 色に着色し、その後vを戻して、隣接する色とは異なる色を選択することで 4 色に着色を拡張できるためです。

Kempe は、 G が次数 4 の頂点を持たないことも正しく示しました。前と同様に、頂点v を削除し、残りの頂点を 4 色に着色します。v の 4 つの隣接頂点がすべて異なる色 (時計回りの順に赤、緑、青、黄色など) である場合、赤と青の隣接頂点を接続する赤と青の色の頂点の交互パスを探します。このようなパスはKempe チェーンと呼ばれます。赤と青の隣接頂点を接続する Kempe チェーンがある場合もあれば、緑と黄色の隣接頂点を接続する Kempe チェーンがある場合もありますが、両方が存在することはありません。これは、これら 2 つのパスが必ず交差し、交差する頂点を着色できないためです。連鎖していないのは赤と青の隣接頂点であるとします。赤と青の交互パスによって赤の隣接頂点に接続されているすべての頂点を調べ、これらすべての頂点で赤と青の色を反転します。結果は依然として有効な 4 色着色であり、v を戻して赤に着色できます。

この場合、 G に次数 5 の頂点がある場合だけが残りますが、Kempe の議論はこの場合には不完全でした。Heawood は Kempe の間違いに気づき、5 色だけが必要であることを証明するだけで満足するのであれば、上記の議論を実行し (最小の反例には 6 色が必要であるという点だけを変更して)、次数 5 の状況で Kempe 連鎖を使用して5 色定理を証明できると指摘しました。

いずれにせよ、この次数 5 の頂点のケースを扱うには、頂点を削除するよりも複雑な概念が必要です。むしろ、議論の形式は、各頂点 (G 内) の次数が指定された、 Gの連結されたサブグラフである構成 を考慮するように一般化されます。たとえば、次数 4 の頂点の状況で説明したケースは、G内で次数 4 とラベル付けされた単一の頂点で構成される構成です。上記のように、構成を削除して残りのグラフを 4 色にした場合、構成を再度追加したときに 4 色をそれにも拡張できるように色を変更できることを示すだけで十分です。これが可能な構成は、縮小可能な構成と呼ばれます。構成の集合の少なくとも 1 つが G 内のどこかで発生する必要がある場合、その集合は不可避的と呼ばれます。上記の議論は、5 つの構成の避けられないセット (次数 1 の単一の頂点、次数 2 の単一の頂点、...、次数 5 の単一の頂点) を示すことから始まり、次に最初の 4 つが簡約可能であることを示しました。セット内のすべての構成が簡約可能である避けられない構成セットを示すことで、定理が証明されます。

Gは三角形なので、構成内の各頂点の次数は既知であり、構成内のすべての辺は既知であり、特定の構成に隣接するG内の頂点の数は固定されており、それらは閉路に結合されます。これらの頂点は構成のリングを形成します。リング内にk個の頂点を持つ構成はkリング構成であり、構成とそのリングを合わせたものはリング構成と呼ばれます。上記の単純なケースと同様に、リングのすべての異なる 4 色付けを列挙できます。構成の色付けに変更なしで拡張できる色付けは、初期良好と呼ばれます。たとえば、上記の 3 つ以下の近傍を持つ単一頂点構成は、初期良好でした。一般に、リングの色付けを良好な色にするには、周囲のグラフを体系的に再色付けする必要があります。これは、上記の 4 つの近傍がある場合に行われたのと同じです。より大きなリングを持つ一般的な構成の場合、これにはより複雑な手法が必要です。リングには 4 つの異なる色付けが多数あるため、これがコンピューターの支援を必要とする主なステップです。

最後に、この手順で削減できる避けられない構成のセットを識別する必要があります。このようなセットを見つけるために使用される主な方法は、放電方法です。放電の根底にある直感的なアイデアは、平面グラフを電気ネットワークとして考えることです。最初は、正と負の「電荷」が頂点間で分配され、合計が正になります。

上記の式を思い出してください。

${\displaystyle \sum _{i=1}^{D}(6-i)v_{i}=12.}$

各頂点には、6 度 ( v ) の初期電荷が割り当てられます。次に、一連の規則 (放電手順)に従って、頂点から隣接する頂点に電荷を系統的に再分配することで、電荷を「流し」ます。電荷は保持されるため、一部の頂点にはまだ正の電荷があります。この規則により、正に帯電した頂点の構成の可能性が制限されるため、そのような可能な構成をすべて列挙すると、避けられない集合が得られます。

不可避セットの一部のメンバーが縮小不可能な限り、排出手順はそれを排除するように修正されます (他の構成を導入しながら)。アペルとハーケンの最終的な排出手順は非常に複雑で、結果として生じる不可避構成セットの説明とともに 400 ページのボリュームを占めていましたが、生成された構成は機械的に縮小可能であることが確認できました。不可避構成セット自体を説明するボリュームの検証は、数年にわたるピアレビューによって行われました。

ここでは説明しませんが、証明を完了するために必要な技術的な詳細は、浸漬還元可能性です。

四色定理は、その長い歴史の中で、多数の誤った証明と反証を引き起こしてきたことで悪名高い。当初、ニューヨークタイムズは、方針として、アペル・ハーケンの証明が以前のものと同様に誤りであると示されることを恐れ、その証明について報道することを拒否した。^[21]前述のケンプやテイトの証明のように、いくつかの疑わしい証明は、反証されるまで10年以上もの間、世間の精査にさらされていた。しかし、アマチュアによって書かれた証明の多くは、まったく公表されなかった。

一般的に、最も単純だが無効な反例は、他のすべての領域に接する 1 つの領域を作成しようとします。これにより、残りの領域は 3 色のみで色付けされることになります。4 色定理は正しいため、これは常に可能ですが、地図を描く人は 1 つの大きな領域に集中しているため、残りの領域を実際には 3 色で色付けできることに気付きません。

このトリックは一般化できます。一部の領域の色が事前に選択されている場合、残りの領域を 4 色を超えずに色付けすることは不可能になるマップが多数あります。反例を偶然検証する人は、反例が有効であるように見えるようにこれらの領域の色を変更することを考えないかもしれません。

おそらく、このよくある誤解の根底にある効果の 1 つは、色の制限が推移的ではないという事実です。つまり、領域は、直接接している領域と異なる色にすればよく、接している領域に接している領域と異なる色にする必要はありません。これが制限であれば、平面グラフには任意の数の色が要求されます。

その他の誤った反証は、複数の切断された部分で構成される領域を使用したり、同じ色の領域が 1 点で接触することを許可しないなど、定理の仮定に違反します。

あらゆる平面地図は4色で着色できるが、任意の平面地図を3色だけで着色できるかどうかを判断するのはNP完全な計算量である。 ^[29]

立方体の地図は、各内部領域に隣接する領域が偶数個ある場合にのみ、3色のみで色付けすることができます。^[30]米国の州の地図の例では、内陸のミズーリ州( MO ) には 8 つの隣接州 (偶数) があり、そのすべてと異なる色にする必要がありますが、隣接州は交互に色を付けることができるため、地図のこの部分には 3 色のみが必要です。一方、内陸のネバダ州( NV ) には 5 つの隣接州 (奇数) があり、その 1 つの隣接州は、その隣接州と他のすべての隣接州とは異なる色にする必要があるため、ここでは 4 色が必要です。

4色定理は有限平面グラフだけでなく、平面上で交差することなく描くことができる無限グラフにも適用され、さらに一般的には、すべての有限部分グラフが平面である無限グラフ（おそらく無数の頂点を持つ）にも適用されます。これを証明するには、有限平面グラフの定理の証明と、無限グラフのすべての有限部分グラフがk色可能である場合、グラフ全体もk色可能であるというド・ブリュイン・エルデシュの定理（1967年）を組み合わせることができます。これは、無限グラフの彩色可能性を一連の論理式で表現するだけで、 クルト・ゲーデルの第一階述語論理のコンパクト性定理から直接導かれるものと見なすこともできます。

平面以外の表面上の着色問題も考えることができる。^[31]球面や円筒面上の着色問題は平面上の着色問題と同等である。正の種数を持つ閉じた（向き付け可能または向き付け不可能な）表面の場合、必要な色の最大数pは、表面のオイラー特性χに依存し、次の式で表される。

${\displaystyle p=\left\lfloor {\frac {7+{\sqrt {49-24\chi }}}{2}}\right\rfloor ,}$

ここで、最も外側の括弧は床関数を表します。

あるいは、有向面の場合、式は面の種数gで表すことができます。

${\displaystyle p=\left\lfloor {\frac {7+{\sqrt {1+48g}}}{2}}\right\rfloor .}$

この公式、ヒーウッド予想は、1890 年にPJ ヒーウッドによって提唱され、数人の貢献を経て、 1968 年にゲルハルト リンゲルとJWT ヤングによって証明されました。この公式の唯一の例外はクラインの壷で、これはオイラー標数が 0 である (したがって、公式では p = 7 となる) ものの、1934 年にフィリップ フランクリンによって示されたように、6 色のみを必要とします。

たとえば、トーラスのオイラー特性 χ = 0 (種数g = 1) とp = 7 があるため、トーラス上の任意のマップを色付けするには 7 色以上は必要ありません。この 7 という上限は明確です。シラッシ多面体などの特定のトーラス多面体には 7 色が必要です。

メビウスの帯には6 色が必要です (Tietze 1910) 。1 平面グラフ(1 辺につき最大 1 つの単純な交差で描画されるグラフ) も同様です (Borodin 1984)。平面グラフの頂点と面の両方に色を付ける場合、隣接する 2 つの頂点、面、または頂点と面のペアが同じ色にならないようにすると、やはり最大 6 色が必要になります (Borodin 1984)。

• 
  放射状に対称な7色のトーラス – 同じ色の領域が点線に沿って囲まれている
• 
  8色の二重トーラス（種数2の表面） – 泡は2つの領域のユニークな組み合わせを表す
• 
  9色の三重トーラス（種数3の表面） – 斑点はそれぞれのトンネルの端を表します
• 
  6色のクラインの瓶
• 
  ティーツェはメビウスの帯を 6 つの互いに隣接する領域に分割します。これには 6 つの色が必要です。分割の頂点と辺は、帯へのティーツェのグラフの埋め込みを形成します。
• 
  7つの面が互いに隣接したインタラクティブなシラッシ多面体モデル - SVG画像では、マウスを動かすと回転します。

頂点が2つの異なる面上の点のペアとして表され、辺が2つの面の1つに交差しない曲線として描かれているグラフの場合、彩色数は少なくとも9、最大で12であるが、より正確な境界は知られていない。これはゲルハルト・リンゲルの地球-月問題である。^[32]

色付けの結果が3次元の立体領域に拡張されるという明らかな方法はありません。n本の柔軟な棒のセットを使うと、すべての棒が他のすべての棒に接するように配置できます。その場合、セットにはn色、またはすべての棒に接する空きスペースを含めてn +1色が必要になります。nの数は任意の整数にすることができ、必要なだけ大きくなります。このような例は1880年にフレデリック・ガスリーによって知られていました。^{[33]軸が平行な}直方体（2つの直方体が2次元の境界領域を共有する場合、隣接していると見なされます）の場合でも、無制限の数の色が必要になる場合があります。^[34]

ドロール・バルナタンは、リー代数とヴァシリエフ不変量に関して、四色定理と同等の声明を出した。 ^[35]

国の政治地図を色分けするという動機にもかかわらず、この定理は地図製作者にとって特に興味深いものではない。数学史家ケネス・メイの論文によると、「4色のみを使用する地図はまれであり、通常、3色のみで済む。地図製作と地図製作の歴史に関する本では、4色の性質については触れられていない」。^[36]また、この定理は、同じ国の隣接していない地域（アラスカの飛び地と米国の残りの地域など）を同じ色にするという通常の地図製作要件を保証するものではない。4色定理は地図上の地域が隣接していない場合には適用されないため、世界地図にも適用されない。世界地図では、オランダがサン・マルタン島でフランスと国境を接しているため、海、ベルギー、ドイツ、オランダ、フランスはすべて互いに隣接している。これが唯一の反例である。^[要出典]

• アポロニアンネットワーク
• 五色定理
• グラフの色付け
• Grotzsch の定理:三角形のない平面グラフは 3 色可能である。
• ハドヴィガー・ネルソン問題: 単位距離離れた 2 つの点が同じ色にならないように平面を着色するには、何色必要でしょうか?

ウィキメディア・コモンズには、四色定理に関連するメディアがあります。

• 「4色問題」、数学百科事典、EMS Press、2001 [1994]

• MathOverflowの 4 色定理の一般化のリスト