四色定理
4色マップの例
湖と海を無視した、アメリカ合衆国の州の4色地図

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

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

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

処方

地図の彩色はグラフ理論の観点からも述べることができ、領域間の隣接関係を表す平面グラフのグラフ彩色を構成するという観点から考察することができます。グラフ理論的な用語で言えば、この定理は、ループのない平面グラフ（その彩色数で表される）に対して、が成り立つことを述べています。 G{\displaystyle G}χ（G）{\displaystyle \chi (G)}χ（G）≤4{\displaystyle \chi (G)\leq 4}

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

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

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

4 つの領域を持つマップと、それに対応する 4 つの頂点を持つ平面グラフ。

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

歴史

初期の証明の試み

ド・モーガンからウィリアム・ローワン・ハミルトンへの手紙、1852年10月23日

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

私の学生[ガスリー]が今日、私が事実だと知らなかった、そして今も知らない事実の理由を尋ねてきました。彼によれば、図形を分割し、区画ごとに異なる色を塗ることで、共通の境界線の一部を持つ図形が異なる色に塗られる場合、4色は必要だがそれ以上は必要ではない、とのことです。以下は、4色が必要な例です。5色以上の必要性を発明できるでしょうか… [ 8 ]

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

この定理を証明しようとする初期の試みはいくつかあったが、いずれも失敗に終わった。ド・モルガンは、この定理が4つの領域に関する単純な事実から導かれると信じていたが、より基本的な事実からその事実を導くことは不可能だと考えていた。

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

1つの提案された証明は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色で塗りつぶせないため、元の地図は最小ではありません。

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

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

1980年代初頭、アペル＝ハーケンの証明に欠陥があるという噂が広まった。アーヘン工科大学のウルリッヒ・シュミットは、1981年に出版された修士論文のためにアペルとハーケンの証明を精査した。 [ 24 ]彼は不可避性の部分の約40%をチェックし、排出手順に重大な誤りを発見した（アペル＆ハーケン1989 ）。1986年、アペルとハーケンは数学インテリジェンサーの編集者から、彼らの証明の欠陥の噂に対処する記事を書くように依頼された。彼らは、噂は「（シュミットの）結果の誤解」によるものだと答え、詳細な記事を書いた。[ 24 ]彼らの最高傑作である『すべての平面地図は4色可能』は、完全で詳細な証明であると主張した本（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年、ベンジャミン・ヴェルナーとジョルジュ・ゴンティエは、 Rocq （旧称Coq）証明支援システム内で定理の証明を形式化しました。これにより、特定のケースを検証するために用いられる様々なコンピュータプログラムを信頼する必要がなくなり、Rocqカーネルのみを信頼すればよくなりました。[ 28 ]

証明のアイデアの要約

以下の議論は、 Appel & Haken 1989 の序文に基づく要約です。ケンプによる四色定理の当初の証明は、欠陥はあるものの、後に四色定理を証明するために用いられる基本的なツールの一部を提供しました。ここでの説明は、上記の現代グラフ理論の定式化に基づいて言い換えられています。

ケンプの議論は以下の通りである。まず、グラフによって区切られた平面領域が三角形化されていない場合（つまり、境界内にちょうど3つの辺を持たない場合）、新しい頂点を追加することなく辺を追加することで、境界のない外側の領域を含むすべての領域を三角形にすることができる。この三角形化されたグラフが4色以下で彩色可能であれば、辺を削除しても同じ彩色が有効であるため、元のグラフも同様に彩色可能である。したがって、三角形化されたグラフの4色定理を証明すれば、すべての平面グラフに対して証明でき、一般性を損なうことなくグラフが三角形化されていると仮定できる。

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

6v−2e＝6∑私＝1Dv私−∑私＝1D私v私＝∑私＝1D（6−私）v私＝12.{\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の頂点を持つ場合のみであるが、ケンプの議論はこのケースには欠陥があった。ヒーウッドはケンプの誤りに気づき、もし5色のみが必要であることを証明するだけで満足するのであれば、上記の議論を（最小の反例が6色であることだけを変更して）繰り返し、次数5の状況でケンプ連鎖を用いて5色定理を証明できると指摘した。

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

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

最後に、この手順によって縮約可能な避けられない構成の集合を特定することが残っています。そのような集合を発見するために用いられる主な方法は、放電法です。放電法の根底にある直感的な考え方は、平面グラフを電気ネットワークと見なすことです。最初は、正と負の「電荷」が頂点間に分配され、合計が正になります。

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

∑私＝1D（6−私）v私＝12.{\displaystyle \sum _{i=1}^{D}(6-i)v_{i}=12.}

次数の各頂点には、初期電荷が割り当てられます。次に、一連の規則（放電手順）に従って、頂点から隣接する頂点へ電荷を系統的に再分配することで、電荷を「流す」ことができます。電荷の総量は最初は正電荷（12）であり、電荷は保持されるため、一部の頂点はまだ正電荷を保持しています。これらの規則は、正電荷を持つ頂点の配置の可能性を制限するため、そのような可能性のある配置をすべて列挙すると、避けられない集合が得られます。 私{\displaystyle i}6−私{\displaystyle 6-i}

不可避集合の要素が還元不可能な場合、排出手順はそれを除去するように修正され（同時に他の構成を導入する）、その要素は除去される。アペルとハーケンの最終的な排出手順は非常に複雑で、結果として生じる不可避構成集合の記述と合わせて400ページに及ぶ書籍となったが、生成された構成は機械的に還元可能であることが確認できた。不可避構成集合自体を記述した書籍の検証は、数年にわたる査読によって行われた。

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

誤った反証

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

最初のマップは4色を超えるため、赤い領域を他の4色のいずれかに置き換えることはできず、一見すると定理に反しているように見えるかもしれません。しかし、2番目のマップに示すように、色を並べ替えることは可能です。

一般的に、最も単純だが妥当ではない反例は、他のすべての領域に接する一つの領域を作ろうとするものです。これにより、残りの領域は3色でしか塗りつぶせなくなります。四色定理が成り立つため、これは常に可能です。しかし、地図を描く人は一つの大きな領域に集中しているため、残りの領域を実際には3色で塗りつぶせることに気づきません。

このトリックは一般化できます。多くの地図では、一部の領域の色が事前に選択されていると、残りの領域を4色を超えずに塗りつぶすことができなくなります。反例を適当に検証する人は、これらの領域の色を変更しようとは思わないかもしれません。そうしないと、反例が正当であるかのように見えてしまうからです。

このよくある誤解の根底にある影響の一つは、色の制約が推移的ではないという事実にあるのかもしれません。つまり、ある領域は、直接接する領域とのみ異なる色で塗られればよく、接する領域に接する領域と異なる色で塗られる必要はありません。もしこれが制約であれば、平面グラフには膨大な数の色が必要になるでしょう。

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

三色塗り

米国の州の地図には少なくとも 4 色が必要であることを言葉なしで証明します。

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

立方体の地図は、各内部領域が偶数個の隣接領域を持つ場合のみ、3色で塗りつぶすことができます。[ 30 ]アメリカの州の地図の例では、内陸のミズーリ州（MO）は8つの隣接州（偶数）を持っています。MOはそれらすべてと異なる色で塗る必要がありますが、隣接州は交互に色を塗ることができます。したがって、地図のこの部分は3色で済みます。一方、内陸のネバダ州（NV）は5つの隣接州（奇数）を持っています。これらの隣接州には3色が必要で、MOはそれらと異なる色で塗る必要があります。したがって、ここでは4色が必要です。

一般化

無限グラフ

単一の矢印と二重の矢印を結合すると、相互に接触する 7 つの領域を持つトーラスが得られます。したがって、7 つの色が必要になります。
この構造は、トーラスが最大 7 つの領域に分割され、各領域が互いに接していることを示しています。

四色定理は有限平面グラフだけでなく、平面上で交差することなく描くことができる無限グラフにも適用され、さらに一般的には、すべての有限部分グラフが平面である無限グラフ（場合によっては無数の頂点を持つ）にも適用されます。これを証明するには、有限平面グラフの定理の証明と、無限グラフのすべての有限部分グラフがk色可能である場合、グラフ全体もk色可能であると述べるDe Bruijn–Erdős の定理( Nash-Williams 1967 ) を組み合わせることができます。これはまた、無限グラフの彩色可能性を一連の論理式で表現するだけで、 Kurt Gödelの第一階述語論理のコンパクト性定理から直接導かれる結果と見なすこともできます。

より高い表面

平面以外の曲面上の彩色問題も考えることができる。[ 31 ]球面や円柱上の彩色問題は平面上の彩色問題と等価である。正の種数を持つ閉曲面（向き付け可能または向き付け不可能）の場合、必要な彩色数の最大値pは曲面の オイラー標数χに依存する。

p＝⌊7+49−24χ2⌋、{\displaystyle p=\left\lfloor {\frac {7+{\sqrt {49-24\chi }}}{2}}\right\rfloor ,}

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

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

p＝⌊7+1+48グラム2⌋。{\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つの単純交差で描画されるグラフ）にも6色が必要です ( Borodin 1984 )。平面グラフの頂点と面の両方に色を塗り、隣接する2つの頂点、面、または頂点と面のペアが同じ色にならないようにする場合も、最大6色が必要です ( Borodin 1984 )。

実射影平面のオイラー特性はχ = 1であり、式ではp = 6となるため、必要な色は 6 色以下です。

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

固体領域

3次元以上では必要な色の数は無限であることを言葉なしで証明する

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

他の数学分野との関係

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

数学以外の用途

カリブ海北東部の島、サン・マルタン島はフランスとオランダに分割されています。

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

この定理は、すべての水域に国名に使用できない色（例えば青）を割り当てることを要求した場合にも適用されません。その場合、ヨーロッパの地図自体は4色で表すことができません。フランス、ドイツ、ベルギーは互いに隣接しているため、それぞれ異なる3色を割り当てる必要があり、合計4色となります。フランスとオランダには同じ色を割り当てることができますが、ルクセンブルクには5色目が必要です。[ 38 ]

参照

注記

  1. ^ Gonthier (2008)より：「定義：平面写像とは、平面上の互いに素な部分集合（領域）の集合である。単純写像とは、領域が連結された開集合である写像である。写像の2つの領域は、それぞれの閉包が写像の角ではない共通点を持つ場合、隣接している。ある点が写像の角であるためには、少なくとも3つの領域の閉包に属する必要がある。定理：任意の単純平面写像の領域は、隣接する2つの領域が異なる色になるように、4色のみで彩色できる。」
  2. ^スワート（1980） .
  3. ^ウィルソン（2014）、216-222。
  4. ^ハドソン (2003) .
  5. ^ Thomas (1998 , p.849); Wilson (2014 ) .
  6. ^メビウスが四色予想を考案したという数学的な言い伝えがあるが、この考えは誤りであると思われる。ノーマン・ビッグス、E・キース・ロイド、ロビン・J・ウィルソン（1986年）『グラフ理論 1736–1936』オックスフォード大学出版局、116ページ、ISBNを参照。 0-19-853916-9マディソン、イザベル（1897）「地図彩色問題の歴史に関するノート」アメリカ数学会誌、3（7）：257、doi：10.1090/S0002-9904-1897-00421-9
  7. ^ドナルド・マッケンジー著『証明の機械化：コンピューティング、リスク、そして信頼』（MIT Press、2004年）p103
  8. ^ウィルソン（2014）、12ページ。
  9. ^ FG (1854) ;マッケイ (2012)
  10. ^ a bデ・モーガン（匿名）、オーガスタス（1860年4月14日）「発見の哲学、歴史的および批判的章。W・ヒューウェル著」、アテネウム：501–503
  11. ^ WW Rouse Ball (1960)「四色定理」、Mathematical Recreations and Essays、Macmillan、ニューヨーク、pp 222–232。
  12. ^トーマス（1998）、848ページ。
  13. ^ヒーウッド（1890） .
  14. ^テイト (1880) .
  15. ^ハドヴィガー（1943年）。
  16. ^ウィルソン（2014）、139–142頁。
  17. ^ゲイリー・チャートランドとリンダ・レスニアック、 Graphs & Digraphs (CRC Press、2005) p. 221
  18. ^ウィルソン（2014）、145–146頁。
  19. ^ウィルソン (2014、pp. 105–107);アペル＆ハーケン (1989) ;トーマス (1998、pp. 852–853)
  20. ^ a bアペル＆ハケン（1989）。
  21. ^ a bウィルソン（2014）、153ページ。
  22. ^ウィルソン（2014）、150頁。
  23. ^ウィルソン（2014）、157頁。
  24. ^ a bウィルソン（2014）、165頁。
  25. ^ Thomas (1995) ; Robertson et al. (1996) .
  26. ^トーマス（1998）、852-853頁。
  27. ^ Thomas (1999) ; Pegg et al. (2002) .
  28. ^ゴンティエ (2008) .
  29. ^ Dailey, DP (1980)、「平面4正則グラフの彩色可能性の一意性と彩色可能性はNP完全である」、離散数学、30 (3): 289– 293、doi : 10.1016/0012-365X(80)90236-8
  30. ^ Steinberg, Richard (1993)、「三色問題の現状」、Gimbel, John; Kennedy, John W.; Quintas, Louis V. (編)、『Quo Vadis, Graph Theory?』、Annals of Discrete Mathematics、vol. 55、アムステルダム：North-Holland、pp.  211– 248、doi：10.1016/S0167-5060(08)70391-1、ISBN 978-0-444-89441-0、MR  1217995
  31. ^リンゲル（1974年）。
  32. ^ゲトナー、エレン（2018年）「月とその先へ」ゲラ、ラルッカ、テレサ・W・ヘインズ、スティーブン・T・ヘデトニエミ（編）、グラフ理論：お気に入りの予想と未解決の問題II、数学の問題集、シュプリンガー・インターナショナル・パブリッシング、pp.  115– 133、doi：10.1007/978-3-319-97686-0_11、ISBN 978-3-319-97684-6、MR  3930641
  33. ^ウィルソン（2014）、15ページ。
  34. ^リード＆オールライト 2008 ;マグナント＆マーティン (2011)
  35. ^バーナタン（1997） .
  36. ^ウィルソン (2014)、2.
  37. ^ウィルソン (2014)、6.
  38. ^ Coxeter, HSM (1971年夏)、「地図の色付けの数学」、Leonardo、4 (3): 273– 277、doi : 10.2307/1572306、JSTOR 1572306 

参考文献

ウィキメディア・コモンズには、四色定理に関連するメディアがあります。
「 https://en.wikipedia.org/w/index.php?title=Four_color_theorem&oldid=1333214225」より取得