グラフ理論の彩色問題

質問

G を3 角形がない単純平面的グラフとする．このとき，G が4-彩色可能であることを示せ．

この問題の証明が出来なくて困ってます。
誰かわかりやすく解説お願いします。

回答No.3

pori_boy

こんにちは．

色々な手順があるかもしれませんが，まず，以下の問題の証明は出来ますか？

G を単純平面的グラフとする．このとき，G が6-彩色可能であることを示せ．

この問題の証明が自分で出来る（もしくは証明を理解できる）のであれば，
質問の問題の証明も出来るのではないかなと思います．

回答No.2

Tacosan

「こういう丸投げ　が一番困る」の部分は #1 に同意.
そして, できないなら素直に「できない」って言ったほうがいいと思う.

少なくとも, 個人的には「どうすれば証明できるのか」が思いつかない. #1 の方針でいいのかもしれんけど, なんというか, 超大質量ブラックホール並みの落とし穴が掘ってあるように見えるんだよね....

回答No.1

B-juggler

こういう丸投げ　が一番困るね。

代数学の非常勤講師ね（病気療養だけど）。

「どこまで分かっているのか」が分からないから、

どっから書いていいのかわからないんですよ。

４色問題だから、「どういう状況のグラフであれば　４色でいい」というのが

分かっていないようです。

単純平面グラフ　って何かをまず見直して。

それを理解して、　「三角形を含まない　単純平面グラフ」が理解できれば

証明も何も必要のないくらいに簡単なんだよ？

う～ん、この頃、大学生も丸投げするなぁ～。

σ(・・*)が教えていた頃も、そうだったのかな？

ｍ（＿　＿）ｍ