■ラムゼー数(その8)

 グラフが平面的とはどの辺も交わらないように平面上に描ける場合をいう.完全グラフKn(辺数:n(n−1)/2)が平面的であるための必要十分条件はn≦4である.

 K5やK3,3は平面グラフではない.グラフが平面的であるための必要十分条件はKかK3,3と同型の部分グラフを含まないことである(クラトウスキー).

===================================

 K5は平面グラフではないが,2つの平面グラフに分割することができる.

  E(K5)=2

 n≠4 (mod6)のとき,

  E(Kn)=[(n+7)/6]

であることが示されている.

 また,

  E(K4)=1,E(K10)=3,E(K22)=4,

  E(K28)=5,E(K34)=6,E(K40)=7

であることがわかっている.

===================================