いつでも医師に相談、gooドクター

4色定理について質問です。
4色定理とは
・全ては地図は4色で塗り分けられる
→平面グラフは4色で塗り分けられる
・平面グラフはどの辺も交差しないグラフ

つまり平面上にある全ての図形が、他の全ての図形と接し合うことができるのは4つまで。(5つ以上の図形が他の全ての図形と接し合うことはできない)
→平面グラフの全ての頂点が他の全ての頂点と繋がり合うことができるのは4点まで。(5つ以上頂点を持つ平面グラフは、全ての頂点が他の全ての頂点と交差なく繋がり合うことはできない)

という認識であってますか?
これが正しければコンピュータを使わずシンプルな証明をできるのではないでしょうか。

画像の様に5点の平面グラフは全ての頂点が他の全ての頂点と繋がり合うことはできないと思っています。

私の考え方が間違っているのか、
平面的グラフも考えなければいけないためパターンが膨大なのか
そのように考えた数学者の方でもコンピュータを使わず証明することが難しかったのか教えてください。

よろしくお願いします。

「4色定理について質問です。 4色定理とは」の質問画像
gooドクター

A 回答 (6件)

>なぜ間違っているのかの理由も教えていただけますか?


必要十分条件になっていないということ。
4色定理 → K5は存在しない
ですが、逆は言えないということ。

「K4は存在しないが3色では無理な図形」(No3さんの例)があるので、
「K5は存在しないが4色では無理な図形」もありそうな気がしませんか?
    • good
    • 0
この回答へのお礼

理解できました。ありがとうございます。
ご丁寧に2度もまたわかりやすくお応え頂けましたのでベストアンサーとさせてください。
教えていただいた皆様、ありがとうございました。

お礼日時:2020/12/15 15:38

どこが間違っているかは、No.3 の指摘につきると思う。


あの図の中の4区画を取り出して考えると
どの4区画を取り出しても3色で塗り分け可能だが、
図全体では4色めが必要になる。このように
グラフの塗り分けは、グラフの一部だけを取り出したのでは
見えてこない大域的な性質なので、質問文のように
K5を含むかどうかだけで判定することはできない。

グラフにK5が含まれていれば、もちろん
4色塗り分けできないのは自明だけれど、
K5を含まないからといって、4色塗り分け可能だとは限らない。
K5以外の4色塗り分け不能な部分グラフを含んでいる可能性
はどうなの?という話(要するにNo.1)になる。

実際に行われた4色定理の証明は
グラフのサイズに関する帰納法で示すのだが、
その帰納ステップが1400通りほどの場合分けを含むため
人手ではたいへんなのでコンピューターに検証させた
という代物だった。
    • good
    • 0
この回答へのお礼

ご回答ありがとうございます。
なるほど、そんな大変な作業が行われたのですね。勉強になりました。

お礼日時:2020/12/15 15:40

>ただ疑問が解消できず、どこが間違っているのだろうと思い、質問させていただきました。


「5つの頂点が他の4つの頂点と繋がり合う平面グラフは作れないことを証明できれば、4色定理の問題の証明になる」が間違ってますよ。
    • good
    • 0
この回答へのお礼

ご回答ありがとうございます。なるほど、前提が間違っているのですね。なぜ間違っているのかの理由も教えていただけますか?

お礼日時:2020/12/15 13:06

図のように


どの4つの区域も互いに接していないが
3色で塗り分けられないから
どの5つの区域も互いに接していないからといって
4色で塗り分けられるとはいえません
「4色定理について質問です。 4色定理とは」の回答画像3
    • good
    • 1
この回答へのお礼

ご回答ありがとうございます。
理解が足らず申し訳ありません。いただいた図は全部で6区域に見えるのですが、この中の4区域を取り出して考えるということでしょうか?

お礼日時:2020/12/15 11:22

この問題は,コンピューターでは証明されていますが,それは,ありとあらゆる場合をしらみつぶしにやる方法でなされたものです。


従ってまだ,数学的には証明がされていません。
あなたの証明方法が,正しいのか私には分かりませんが,過去の偉大な数学者でも解けなかった難問が,あなたのような考え方をしたことと思われますので,失礼ですが,この方法ではダメだと思われます。
フェルマーの最終定理が死後330年経って,1995年ワイルズによって証明されたように,他の定理の証明がされて,それを利用して初めて解決するのではないでしょうか?
    • good
    • 0
この回答へのお礼

ご回答ありがとうございます。はい、私は数学者でもなく素人なので、このやり方はおそらくダメなのだろうと思っています。ただ疑問が解消できず、どこが間違っているのだろうと思い、質問させていただきました。

お礼日時:2020/12/15 10:39

「全ての頂点間に辺がある」グラフを完全グラフといって, 特に頂点が n個の完全グラフを K_n と記号で書いたりします. 平面的グラフだと K_5 を含まない, とかね.



で, ひょっとすると
K_n が存在しなければ (高々) n色で塗れる
と思ってませんか?
    • good
    • 1
この回答へのお礼

ご回答ありがとうございます。
数学はちゃんと学んだことのない初心者で、私が勘違いしているかもしれないのですが
5つの頂点全てが交差なく他の4つの頂点と繋がることができれば、5色で塗り分けなければいけないことの証明になると思いつきです。
紙と鉛筆でやってみたところ、4つの頂点の場合までは簡単に平面グラフが作れたのですが
5つの頂点を持つと、とたんに平面グラフが作れず、全ての頂点を繋げようとするとどうしても交差する箇所ができてしまいました。
つまり5つの頂点が他の4つの頂点と繋がり合う平面グラフは作れないことを証明できれば、4色定理の問題の証明になるのではないか、コンピュータを使わず証明できたのではないかと思って質問させていただきました。

お礼日時:2020/12/15 11:02

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人はこんなQ&Aも見ています

gooドクター

このQ&Aを見た人がよく見るQ&A

このカテゴリの人気Q&Aランキング