■フォークマン数(その11)

【4】完全グラフK5の問題

 そのグラフのどの辺も交わらないように平面上に描ける場合を平面的という.もし,K5が平面的であるならば,v=5,e=10.

  f=2+e−v=7

また,各面は少なくとも3つの辺をもたなければならないから,

  21=3f≦2e=20

となって矛盾.

K4は平面的であるが,K5以上は平面的ではないのである.K5は平面的ではないが,2つの平面的グラフに分割できる.

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