完全グラフが平面的となるための証明について

質問

完全グラフKnと完全２部グラフKn,mが平面的となるためのn,mの範囲を求め、証明せよ。
という問題があるのですが証明が分かりません。
完全グラフはn≦4、完全グラフ２部グラフはn=1 or 2。

どなたか証明を教えてください。

回答No.1

Tacosan · ベストアンサー

グラフが平面的であるための必要条件を挙げてみてください.

完全2部グラフだとちょっと条件が変わることにも注意.

補足

グラフが平面的であるための必要十分条件は、K5あるいはK3,3に縮約可能な部分グラフを含まないことである。
ということでしょうか？
しかし、どのようにしてnの条件不等式を導出できるのでしょうか？

回答No.2

Tacosan

おっと, 書きすぎた.

「完全2部グラフだとちょっと条件が変わることにも注意」のところ, 最初の「完全」は無視してください.