質問: 4色定理について質問です。 4色定理とは ・全ては地図は4色で塗り分けられる →平面グラフは4色で塗 4色定理について質問です。 4色定理とは ・全ては地図は4色で塗り分けられる →平面グラフは4色で塗り分けられる ・平面グラフはどの辺も交差しないグラフ つまり平面上にある全ての図形が、他の全ての図形と接し合うことができるのは4つまで。(5つ以上の図形が他の全ての図形と接し合うことはできない) →平面グラフの全ての頂点が他の全ての頂点と繋がり合うことができるのは4点まで。(5つ以上頂点を持つ平面グラフは、全ての頂点が他の全ての頂点と交差なく繋がり合うことはできない) という認識であってますか? これが正しければコンピュータを使わずシンプルな証明をできるのではないでしょうか。 画像の様に5点の平面グラフは全ての頂点が他の全ての頂点と繋がり合うことはできないと思っています。 私の考え方が間違っているのか、 平面的グラフも考えなければいけないためパターンが膨大なのか そのように考えた数学者の方でもコンピュータを使わず証明することが難しかったのか教えてください。 よろしくお願いします。
回答: 「全ての頂点間に辺がある」グラフを完全グラフといって, 特に頂点が n個の完全グラフを k_n と記号で書いたりします. 平面的グラフだと k_5 を含まない, とかね. で, ひょっとすると k_n が存在しなければ (高々) n色で塗れる と思ってませんか?