- ベストアンサー
グラフ理論
Gが三角形を持たない単純平面的グラフとすると、Gが４－彩色可能であることを帰納法を用いて証明するんですけど、「ｍ≦２ｎ－４」と「次数３以下の頂点がある」の二つで帰納法のやり方を教えてください。
- みんなの回答 （1）
- 専門家の回答
質問者が選んだベストアンサー
三角形を持たない単純平面的グラフについて, １．どの頂点を取り除いてもやはり三角形を持たない単純平面的グラフである ２．次数が高々 3 の頂点が必ず存在する ことが言えれば, 頂点数に関する帰納法で終了じゃない? まあ, きちんと考えたわけじゃないけど. でも, m ≦ 2n-4 って条件は必要なのかなぁ.... ２ を証明するためにはあった方がいいけど....
お礼
わかりました！！ ありがとうございます