グラフ、四色問題

質問

この証明は、コンピューターでは証明されてるみたいですが、手法では証明できないのでしょうか？次数が４の場合までは証明でき、次数が５の場合は判例が見つけられたとありますが、その判例を正した証明はないのでしょうか？もしあれば、教えてください。

回答No.2

tadys · ベストアンサー

4色問題については、参考URLが分かりやすいでしょう。
4色問題の歴史は以下のようになりますが、質問の「次数が5の場合の反例」は
ケンペの証明に対するヒーウッドの反例のことでしょう。
ケンペの証明は比較的簡単ですので専門家でなくても追いかけることが出来ます。
もっとも、完璧に証明しようとすると専門的知識が必要になるようです。

アッペルとハーケンの証明は、地図を１４００種類ほどに分類し、
そのそれぞれが４色で塗り分けられることを確認するというもので、
コンピューターを使用しないと実際的な時間では解決できないでしょう。

1852　ド・モルガンがハミルトンに手紙で質問
1879　ケンペが「証明」を発表
1890　ヒーウッドがの上記「証明」の間違いを指摘
1977　アッペルとハーケンによる証明

参考URL：

http://www.lab2.kuis.kyoto-u.ac.jp/~itohiro/lecture/C6_Coloring.pdf

回答No.1

quantum2000

四色問題はコンピュータの計算力を借りて、３０年も前に「証明」されましたが、
「普通の形の証明」が不可能である、ということは証明されていませんから！？、
将来はそうした「証明」も見つかるかもしれませんね。
それを誰もが望んでいる訳ですし・・・

ところで、質問者さんが書かれている「次数が４の場合」とか「次数が５の場合」
というのは、どのことを指しているのでしょうか？
「次数」というのは、「塗り分けるのに最低限必要な色の数」というような意味でしょうか？

また、「“反例”を正した証明」というのは、どのようなことを指しているのでしょうか？
「塗り分けるのに５色がどうしても必要な地図が存在する」という事の証明でしょうか？