４色定理はなぜグラフ理論で証明できないのでしょうか

質問

４色定理についてですが、引っかかるところがあります。

現在はコンピュータで量的な証明がなされていると聞きますが、グラフ理論で証明されたという話は聞きません。
私の中ではグラフ理論で簡単に説明できるのではないかな、という甘い考えがあります（内容は下記に記載しました）。
ただ、こうした考えは以前もたくさんあって否定されているのだと思います。そこで何が悪いのかを教えて頂きたいのです。
納得できる回答が無かった場合は、私は私の考えが正しいんじゃないかと思っているので、私の胸の内で「私の考えで正しいのだ」と自己完結しようと思います。

この質問の内容は、「下記のようなグラフ理論の考え方で5色の塗りわけは無理＝４色の塗りわけで事足りるので、二次元における地図の塗りわけは４色が最大値であり、４色でことたりる」ということの説明ではどこか不足があるのだろう、その不備を教えて頂ければ、というのが論旨となります。
内容は極めて簡単なのですが、文章が少々難しくなってしまいました。ですが、どなたかお付き合い頂ける方、この論旨の問題点をご存知の方、あるいは少しでもこうではないかとおっしゃって頂ける方がいらっしゃいましたら教えて下さい。
尚、万が一の可能性として「こりゃ世紀の大発見也」みたいなこともあるかもしれませんが（とは言いつつも全く期待してません。まあ、今この文章を書きながら自分自身に笑っていますが）、賛同頂ける方、欠点は無い、と言う方もいらっしゃいましたら教えて下さい。
しかし私自身モヤモヤしているのも事実なので、これが正しいのか穴があるのかを教えて頂きたいのです。

＜序論＞
例えば、二次元平面に描かれた任意数のノードとエッジで観察するとき、地図でのいわゆる４色定理の観点から見ると、ノードが国、エッジが国境になります。
もともと４色問題の根源は、地図での色塗りの組み合わせにおいて、本当に必要な色の数として４色が最大値なのか、５色必要なパターンは無いのか、という点が論点であると私は考えています。

つまり、これをグラフ理論から見れば、
・塗りわけが必要なのは、ノードがエッジによって接続されているケース
であり、４色が必要なものは
・４つのノードが「全て」４つともエッジによって接続されているケース
を想定するものです。

そして５色が必要なものは
・５つのノードが「全て」５つともエッジによって接続されているケース
を想定し、これが存在しないことを証明すれば、塗りわけの最大色数は４ということになります。

＜前提などの説明＞
まず根源的な前提として、エッジを延ばすことのできる条件とはなんでしょうか？　
それはノード間において遮蔽物が無いことです。遮蔽物が無いという状況はどんな状況でしょうか。
逆に言えば遮蔽物とは何か、ということなのですが、この地図塗りわけの問題をグラフ理論に適用すると、閉路グラフの「内部」にノードＡを一つプロットし、「外部」にノードＢをプロットします。
今回は地図塗りわけの問題をグラフ問題に展開していますので、エッジ間の交差はありません。
ですので、閉路グラフの内と外にプロットされているノードＡとＢは直接エッジで接続することはできない、というのが前提となります。
三次元での考えではこれらは無視できるのですが、今回は地図塗りわけがお題となるので、二次元平面上での問題となります。

＜本論＞
序文にも書きましたが、
・５つのノードが「全て」５つともエッジによって接続されているケース
を想定し、これが存在しないことを証明すれば、塗りわけの最大色数は４ということになります。

まず一つずつ考えて生きます。
１．２つのノードの場合
　　→存在するノードが互いに全てエッジによって接続されている。
　　　○－○を想像して頂ければＯＫです。
　　　この場合２色必要になります。

２．３つのノードの場合
　　→存在するノードが互いに全てエッジによって接続されている。
　　　正三角形の頂点に○をくっつけた図を想像して頂ければＯＫです。
　　　この場合３色必要になります。

３．４つのノードの場合
　　→存在するノードが互いに全てエッジによって接続されている。
　　　正三角形の頂点に○をくっつけて、その中央に○を描き、
　　　それらが全て互いに接続されている図を想像して頂ければＯＫです。
　　　４つのノードが互いに全てエッジによって接続されているケースはトポロジー的に必ずこのようになると思います。
　　　この場合４色必要になります。

４．５つのノードの場合
　　さて、それでは５つのノードが互いに全てエッジで接続されるケースを考えてみましょう。
　　実は上記３．「４つのノードの場合」で閉路グラフが構成されており、どこに５つ目のノードをプロットしようとも、その閉路の中の全てのノードにエッジを届かせることはできません。

　ここでは前提として頂点Ａ、Ｂ、Ｃからなる正三角形と、その中央に位置する点Ｄ、そしてこれらの点をノードとし、全て互いにエッジで接続しあったグラフを用います。
　そして５つ目の点Ｅを任意の位置にプロットし、ノードのＡＢＣＤＥが５つ全て互いにエッジで接続できたなら、地図の塗りわけとして５色必要、こうしたモデルがグラフでできないと証明できたなら５つは必要でなく、地図の塗りわけとしての最大必要色数は４色ということになります。

　点Ｅを置く位置としてはグラフ図中の任意の位置となりますが、これを分類すると
　（１）三角形ＡＢＣの外に点Ｅを置く場合
　（２）三角形ＡＢDの内側に点Ｅを置く場合
　（３）三角形ＡCDの内側に点Ｅを置く場合
　（４）三角形BCDの内側に点Ｅを置く場合
　の４種に分けられると思います。

これを一つずつ見ていきましょう。

　（１）三角形ＡＢＣの外に点Ｅを置く場合

　　　点Ｅは、三角形ＡＢＣに構成される閉塞グラフの内側にある点Ｄにエッジが届かない。
　　　よって点Ｅのこの位置のプロットでは、ノードのＡＢＣＤＥが５つ全て互いにエッジで接続できない。

　（２）三角形ＡＢDの内側に点Ｅを置く場合

　　　点Ｅは、三角形ＡＢＤに構成される閉塞グラフの外側にある点Ｃにエッジが届かない。
　　　よって点Ｅのこの位置のプロットでは、ノードのＡＢＣＤＥが５つ全て互いにエッジで接続できない。

　（３）三角形ＡCDの内側に点Ｅを置く場合

　　　点Ｅは、三角形ＡＣＤに構成される閉塞グラフの外側にある点Ｂにエッジが届かない。
　　　よって点Ｅのこの位置のプロットでは、ノードのＡＢＣＤＥが５つ全て互いにエッジで接続できない。

　（４）三角形BCDの内側に点Ｅを置く場合

　　　点Ｅは、三角形BＣＤに構成される閉塞グラフの外側にある点Ａにエッジが届かない。
　　　よって点Ｅのこの位置のプロットでは、ノードのＡＢＣＤＥが５つ全て互いにエッジで接続できない。

以上のことからノードのＡＢＣＤＥが５つ全て互いにエッジで接続できるグラフは存在しない。よって地図塗りわけに対しての必要な最大の色数は４色である。

尚、数学的哲理的考察としては、任意ノード数で、互いに全てのノードをエッジで接続するケースを考えた場合、三つのノードで閉路グラフが形成され、四つ目のノードで「その閉路グラフの内側か外側に」プロットされてしまう。更に上記の例で言えばこの四つ目のノード自体をプロットすることにより、閉路グラフがＡＢＣ、ＡＢＤ、ＡＣＤ、ＢＣＤと四つ形成されてしまう。そしてそこから追加のノード点Ｅをどこに打とうとも、閉路グラフの内側に点Ｅを打てばその外側に、閉路グラフの外側に点Ｅを打てばその内側に、自分とは異なるノードが存在するので、点Ｅからそこのノードに到達するエッジを延ばすことはできない。

となります。

実は、数年前もここで同じような質問をさせて頂いたことはあります。ただ、その時に納得できたように思われたのですが、やはり何か私の心の中でモヤモヤしているものがあったので、再度の質問をさせて頂くことにしました。

どなたかご教授頂ける方がいらっしゃいましたら、宜しくお願い致します。

回答No.6

muturajcp

以下の例では
どの5つのノードも互いに接続されているケースが存在しませんが、
ノードの塗りわけには5色必要です。
ただし局所的にどの5つのノードを取り出しても
エッジが交差しないように2次元展開可能ですが、
2次元の4色定理は証明されているので、
全体的にはエッジが交差して2次元展開不可能です。
どの5つのノードも互いに接続されているケースが存在しないからといって、
エッジが交差しないように2次元展開可能とは限りません。
例)
ノード:
A,B,C,D,E,F,G,H,I

エッジ:
A-B,A-C,A-D,B-C,B-D,C-D,
B-E,C-E,D-E,
A-F,B-F,C-F,
C-G,D-G,E-G,
A-H,B-H,F-H,
E-I,G-I,F-I,H-I

とすると
A,B,C,Dが4つとも接続されているから
A=1
B=2
C=3
D=4
とするとEはB=2,C=3,D=4と接続されているから
E=1
FはA=1,B=2,C=3と接続されているから
F=4
GはC=3,D=4,E=1と接続されているから
G=2
HはA=1,B=2,F=4と接続されているから
H=3
(EとFは接続していない、GとHも接続していないけれども)
IはE=1,F=4,G=2,H=3と接続されているから
I=5
となって
5色必要となります。

回答No.5

tadys

No.3です。

＞＞・しかし、Ｎの数が５よりも十分に大きいＮ個のノードを用意し、そこにランダムにエッジで接続した巨大なグラフを考えたとき、その中の組み合わせにおいて「５つのノードが全て互いに接続しあっている部分が存在しない」＝「５色必要な地図が存在しない」という証明にはなりえない。

５角形の中心と各頂点を結ぶような国の集まりを含む地図が有って、その５カ国を４つの色を使って塗り分けているとします。
そんな地図は存在しえないとするのであれば、その証明が必要です。
中心の点を拡大して５角形とし、周りの５カ国と接続させるとします。（ノードを１個増やす事に相当します）
私が、３色の場合の反例に出した配置ですね。
このままだと、真ん中の国を塗るのに５番目の色が必要になってしまいます。
この地図を４色で塗り分けるのにはどうすればいいのでしょう？
これは、ケンペがこの問題の解決を持って４色問題の解決としたものですが、ヒーウッドの反例によって否定されています。
４角形の国を４色からなる４カ国が取り囲んでいる場合についてはケンペにより解決されています。
http://d.hatena.ne.jp/Polyhedron/20100408/1270732328

ケンペの証明とヒーウッドの反例について調べてみるのが良いでしょう。

４色問題の解説本としては「四色問題」｛ロビン・ウィルソン (著), 茂木 健一郎 (翻訳)｝が出版されています。
http://www.amazon.co.jp/%E5%9B%9B%E8%89%B2%E5%95%8F%E9%A1%8C-%E3%83%AD%E3%83%93%E3%83%B3%E3%83%BB%E3%82%A6%E3%82%A3%E3%83%AB%E3%82%BD%E3%83%B3/dp/4105452010

ロビン・ウィルソンの本より先にブルーバックスから「四色問題」｛一松 信(著) １９７８年｝が出版されています。
この本の付録にはアッペルとハーケンが証明に使用した１８３４個の可約配置を示す [グラフ] が示されています。

可約配置：その国（または国々）を除く地図が４色で塗り分け出来るならば、その国（国々）を追加した全体が４色で塗り分け出来るような国（国々）
自明な可約配置としては、３カ国以下の国で囲まれた国が相当する。

自明でない可約配置を最初に見つけたのはバーコフで、その配置は「バーコフのダイヤモンド」と呼ばれている。
http://ohkawa.cc.it-hiroshima.ac.jp/www32.ocn.ne.jp/~graph_puzzle/1no29.htm

回答No.4

nag0720

＞・しかし、Ｎの数が５よりも十分に大きいＮ個のノードを用意し、そこにランダムにエッジで接続した巨大なグラフを考えたとき、その中の組み合わせにおいて「５つのノードが全て互いに接続しあっている部分が存在しない」＝「５色必要な地図が存在しない」という証明にはなりえない。
＞というように読めましたが合っていますでしょうか。

はい、そのとおりです。

＞つまりは私が書いた５個のノードだけではなく、巨大なグラフにおいてはその辺縁系までもが相互作用しあって最終的に「５つのノードが全て接続しうるようなケースが存在しない」という証明たりえていない、
＞というように理解しましたが、合っていますでしょうか。

いいえ、違います。
「５つのノードが全て接続しうるようなケースが存在しない」ことが証明できていないと言っているのではありません。
そうではなくて、
局所的には４色で十分だとしても、地図全体では５色必要かもしれないということです。

＃３さんも同じようなことを書かれていますが、
「局所的に３色で十分なら、全体でも３色で十分」に反例（１つの国の周りに５つの国が隣接）があるのに、
どうして「局所的に４色で十分なら、全体でも４色で十分」と言えるのかということです。

３色のときの反例をどのように解釈しているのでしょうか？

回答No.3

tadys

４色定理の証明にグラフ理論は使われていますよ。
と言うか、グラフ理論は４色定理の証明に不可欠です。

＞・５つのノードが「全て」５つともエッジによって接続されているケース
＞を想定し、これが存在しないことを証明すれば、塗りわけの最大色数は４ということになります。
平面上に５つのノードが「全て」５つともエッジによって接続されているケースが存在しない事は多面体についてのオイラーの定理を利用すれば簡単に証明できます。
地図の外側全体を一つの国と考えて球面に張り付ければ多面体と等価になります。
５つのノードが「全て」５つともエッジによって接続されているケースはオイラーの定理で簡単に確かめられます。
これが証明になるのであれば、１００年以上続く難問題になる事は無かったでしょう。
この証明で得られるのは５色あれば塗り分けられると言う事だけです。

５つのノードが「全て」５つともエッジによって接続されているケースを言いかえると、５カ国の全てがお互いに接触している地図と言えます。
この様な５カ国が無い地図が４色で塗り分けられるのであれば、お互いに接触する４カ国が無い地図は３色で塗り分けられる事になりますが、お互いに接触する４カ国が無い地図で４色を必要とする地図は有ります。
例えば、５角形の国を５つの国が取り囲んでいる地図です。
もし、お互いに接触する５カ国が無い地図は４色で塗り分けられる事を主張するのであれば、なぜ４カ国の場合は駄目で、５カ国の場合は良いのかを証明する必要があるでしょう。

回答No.2

nag0720

＞５つのノードが全て５つともエッジによって接続されているケースが存在しない　⇒　５色必要なケースもあるかもしれない。
＞この具体例も思い浮かばないのでこちらも分かれば教えて下さい。

実際に４色定理は証明されているわけですから、そんな例は存在しないでしょう。
（もし存在したら定理が間違っていることになってしまう）

５つの国が全て互いに同時に接しているケースが存在しないのは誰にも異論はないと思います。
しかし、局所的に４色で塗れるということと、全体でも４色で塗れるということは別問題です。

例えば、

ある地図があって、どの４つの国を見ても４つの国が全て互いに同時に接しているケースはない。
（つまり、局所的には３色で塗り分けられる）
この地図全体を３色で塗り分けることができるか。

この場合、４色必要になる地図はすぐ見つかると思います。

これと同じように、

ある地図があって、どの５つの国を見ても５つの国が全て互いに同時に接しているケースはない。
この地図は４色で塗り分けられるか。

としたとき、５色必要な地図が存在しないとどうして言い切れるでしょうか？

お礼

再度の回答ありがとうございます。

さて、私の頭は「命題の修辞レトリックがよく分からないからもう納得しちゃえよ」とギブアップ宣言の旗を揚げそうになっているのですが、いやいやここはきちんとチャレンジして行こうと思います。
申し訳ありませんが、お付き合いのほど宜しくお願いします。

> 実際に４色定理は証明されているわけですから、そんな例は存在しないでしょう。
> （もし存在したら定理が間違っていることになってしまう）
了解です。
若干補足する必要がありますが、私としましては「４色定理があるので、この問題は解決したんだね」というスタンスを取っていません。アメリカでの量的な解で解決がはかられたなら、グラフ理論での哲理的解決もできるだろう、それがなされていないのでやってみたいが、ひょっとしたら私の考えと同じ考えをしていた人がいて、どこかでＮＧになっているかもしれない。どこがＮＧなのかを知りたいというのがこの質問の趣旨です。
解や結論ありきで論じたいのではなく、哲理的な考えとして普遍的に通用するか否かの思考にチャレンジしたいのです。
そして心の奥底に、「願わくば『４色問題』における解を量的解ではなく、グラフにおける理論的解によって到達したい」という願望が恥ずかしながら少しだけあります。
宜しくお願いします。

さて、
>５つの国が全て互いに同時に接しているケースが存在しないのは誰にも異論はないと思います。
これはＯＫなのですね。

しかし、

>ある地図があって、どの５つの国を見ても５つの国が全て互いに同時に接しているケースはない。
>この地図は４色で塗り分けられるか。
>
>としたとき、５色必要な地図が存在しないとどうして言い切れるでしょうか？

回答を読んで私なりに整理したのですが、
・私の説明したものはあくまでノードが最高で５つという限定された局所的な理論である。
　これはこれで正しい。
・しかし、Ｎの数が５よりも十分に大きいＮ個のノードを用意し、そこにランダムにエッジで接続した巨大なグラフを考えたとき、その中の組み合わせにおいて「５つのノードが全て互いに接続しあっている部分が存在しない」＝「５色必要な地図が存在しない」という証明にはなりえない。
というように読めましたが合っていますでしょうか。
つまりは私が書いた５個のノードだけではなく、巨大なグラフにおいてはその辺縁系までもが相互作用しあって最終的に「５つのノードが全て接続しうるようなケースが存在しない」という証明たりえていない、というように理解しましたが、合っていますでしょうか。

しかし、まだ疑問に思います。
塗りわけというのは、国と国が国境を接しているとき、その同時接続数のケースが塗りわけの数になります。今回の場合で言うと、グラフに展開できるということです。
グラフに展開できるということは、仮に巨大なグラフがあって互いに５つ同時に接続しているノード群が見つけられなければ証明完了ということになり、それは巨大ノード群Ｎからサンプルのノード群ｎを抽出しても結果は一緒ではないでしょうか。
仮に相互作用して最終的に５つのノードが全て互いに接続しあっているノード群が見つかったとしましょう。しかし、これらはエッジが交差可能なグラフ群ではなく、あくまでエッジが交差不可であるグラフ群からの抽出でありますので、そのノードの抽出数は互いに隣接し合う５つのノードだけで良いはずです。
接続しあうノードが回りまわって最終的に５色必要になる可能性が捨てきれないという考えも簡単に思いつきはするのですが、ただ、それも二次元平面状に展開し、エッジが交差しない条件でのグラフの展開から見れば、５色必要という理論は直接的に隣接していなければなりません。エッジが交差可能であったり、あるいは３以上のｎ次元だったり、トーラスであったりすればこれも考慮しなければならないと思うのですが、今回は「二次元平面状に展開し、エッジが交差しない」という条件が付与されます。即ちｎ色での塗りわけが必要というのは巨大グラフからのノードサンプル抽出であっても、ｎ個の同時「隣接」が必要なのであり、巨大グラフ全体での相互作用を考えなくとも、サンプルを抽出した後の考察で事足りると思うのです。
この考え方はどの辺がダメなのでしょうか？

回答No.1

nag0720

＞そして５色が必要なものは
＞・５つのノードが「全て」５つともエッジによって接続されているケース
＞を想定し、これが存在しないことを証明すれば、塗りわけの最大色数は４ということになります。

サラッと流していますが、問題はここではないですか？

確かに

５つのノードが全て５つともエッジによって接続されているケースがある　⇒　５色必要である

は正しいですが、その逆、

５つのノードが全て５つともエッジによって接続されているケースが存在しない　⇒　５色必要ではない

がどうして正しいと言えるのでしょうか？

お礼

早速の回答ありがとうございます。

うーん・・・。確かにここが煮込めきれていない部分かもしれません。
というよりここをちょっと精査させて下さい。

命題の裏は正しいと言い切れない、ということですよね。
そうすると、
・５つのノードが全て５つともエッジによって接続されているケースが存在しない　⇒　５色必要ではない
というケースは正しいとも言い切れないし、正しくないとも言い切れない、この二つのケースが存在するという理解であってますでしょうか？　
つまりは、
「５つのノードが全て５つともエッジによって接続されているケースが存在しな」くとも、
「５色必要である」ケースの存在がありうるということですよね。

一方、「５つのノードが全て５つともエッジによって接続されているケースが存在しな」い場合には、
「５色での塗りわけは不要である」ケースについては私が質問文で主張している通りです。

ここで少し説明させて下さい。
そもそもグラフにおけるノードの存在自体が、地図における色分けの必要があるという形になります。
もう少し具体的に言いますと、地図上での国がグラフでのノード、地図上での国境がグラフでのエッジになります。国境を接している場合（ノード間にエッジがある場合）は、国と国の区別をつけるために色分けが必要になります。つまり無数に広がるランダムのグラフから任意に抽出したグラフのうち、Ｎ個のノードが互いに全てエッジによってつながっている場合についてはＮ色の塗りわけが必要となります。
これに従うと、「５つのノードが全て５つともエッジによって接続されているケースが存在しな」い場合は、これはすなわち「５色で塗り分けられない」ということにつながると思うのですがいかがでしょうか。

もう少し具体的に言うと、ノード＝国、エッジ＝国境ですので、国境を接している国は塗り分ける必要があります。
４つの国が全て互いに同時に接しているのであれば、４つの塗りわけが必要になります。
５つの国が全て互いに同時に接しているのであれば、５つの塗りわけが必要になりますが、５つの国が全て互いに同時に接しているケースは、質問文に書いた通り、トポロジー上、グラフ理論上、私は存在しないと考えています。

回答に頂いた
「「５つのノードが全て５つともエッジによって接続されているケースが存在しない　⇒　５色必要ではない」がどうして正しいと言えるのでしょうか？」
という文章を勝手に変えさせて頂きますと、
「「５つのノードが全て５つともエッジによって接続されているケースが存在しない　⇒　５色必要ではない」が正しいと言い切れない」
「「５つのノードが全て５つともエッジによって接続されているケースが存在しない　⇒　５色必要ではない」が正しくないケースもありうる」
ということになると思います。

それでは正しくないケースは具体的にどんなものだろう、と考えてみるのですが思い浮かびません。そもそも「５つのノードが全て５つともエッジによって接続されているケースが存在しない　⇒　『５色で塗り分けることが不可能である』＝「５色必要ではない」＝「二次平面上では塗りわけ最大色数は４色でＭＡＸ」」だと思っています。

二次元平面上において互いに全てエッジ接続する閉路グラフを構成するノードの最小数は３であり、閉路の内と外でエッジ接続の疎外が出る数が＋２。つまり、５個のノードでは全て互いにエッジ接続ができない。そして全て互いにエッジ接続が可能なのが、閉路グラフを構成するノードの最小数の３と、閉路グラフの内側、もしくは外側にプロットされるノードの＋１の計４。

よって全て互いにエッジ接続可能なノード数の上限は４である。
そして５つのノードを置いたとき、全て互いにエッジ接続可能なグラフ構成は存在しない。
これをグラフから地図に置き換えた場合、４色の塗りわけだけでよく、５色目は必要無い。

これではダメでしょうか？　

５つのノードが全て５つともエッジによって接続されているケースが存在しない　⇒　５色必要なケースもあるかもしれない。
この具体例も思い浮かばないのでこちらも分かれば教えて下さい。

＜＜追記＞＞
前提条件に次のものを加えさせて下さい。
「互いに全てエッジ接続する閉路グラフ」と書きましたが、閉路じゃないケースも考える必要があるんじゃないか、という回答もあるかと思います。
ただ、「互いに全てエッジ接続するグラフ」については、ノード数が３を超えたとき、これが必然的に閉路構成となることを前提としています。

宜しくお願い致します。