平成26年度：グラフ理論小テスト（第7回） K

平成26年度：グラフ理論小テスト（第7回）
[問１] 位数 p が11以上のグラフ G とその補グラフ G’ について，
その両方が平面グラフになることはない (すくなくともどちらかは
平面的でない)．このことを証明せよ．
ヒント：位数とサイズに関するオイラーの定理を使う
G の位数が 11 の場合について示す．
位数 11 の完全グラフのサイズは 10+9+...2+1 = 55 であり，
これらを二つに分割したとき，一方が G の辺で，他方が G’ の辺となる．
したがって，どちらかは 28 本以上の辺を持つことになる．
よって，G と G’ のうちどちらかはオイラーの公式 q≤3p-6 を満たさず，
平面グラフでない．(G の位数が 12 以上の場合は同様にあきらか)
[問２] 完全グラフ Kn と完全二部グラフ Kn,m が平面的であるための
必要十分条件をそれぞれ求めよ．ただし，単純グラフに限るとする．
K1, K2, K3, K4 は平面に描けるが，オイラーの公式より
K5 は平面的でない．また，それ以上の完全グラフは
K5 を部分グラフとし含むので平面的でない．
以上により n≤4 が必要十分条件．
二部グラフについては，K33は平面的でないので，n,m≥3ならばこれを
部分グラフとして含むので平面的でない．また，n,mのどちらかが
2以下ならば図のように平面グラフとして描ける．
よって，nまたはmが2以下であることが必要十分条件．
...
学籍番号：
氏名：
K2,m
1/1

Download Report