グラフ理論

Gが三角形を持たない単純平面的グラフとすると、Gが４－彩色可能であることを帰納法を用いて証明するんですけど、「ｍ≦２ｎ－４」と「次数３以下の頂点がある」の二つで帰納法のやり方を教えてください。

No.1 ベストアンサー 回答者： Tacosan 回答日時： 2007/09/11 17:17

三角形を持たない単純平面的グラフについて,

１．どの頂点を取り除いてもやはり三角形を持たない単純平面的グラフである
２．次数が高々 3 の頂点が必ず存在する
ことが言えれば, 頂点数に関する帰納法で終了じゃない? まあ, きちんと考えたわけじゃないけど.
でも, m ≦ 2n-4 って条件は必要なのかなぁ.... ２ を証明するためにはあった方がいいけど....

この回答へのお礼

わかりました！！
ありがとうございます

お礼日時：2007/09/17 22:54