■グラフ理論(その1)

完全グラフKnはn個の点のすべての2点を連結させてできるグラフである.したがって,完全グラフKnの頂点数はn,頂点次数はn−1,辺数は(n−1)/2となる.完全グラフKnに三角形は何個あるか? これはnC3で簡単に求めることができる.それでは・・・

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

【1】完全グラフの同色の三角形

完全グラフK5の正五角形を赤線で,星形五角形を青線で結ぶ.この図形には点をつなぐ線がすべて赤かすべて青の三角形は存在しない.しかし,K6のすべての2頂点間を2色の線で結ぶと,点をつなぐ線がすべて赤かすべて青の三角形ができる.したがって,どのような6人の集団でも,3人の友人関係が存在するか,互いに見知らぬ3人が存在することになる.

 色を3色に増やす.K16は同色の三角形が存在しないように配色することができるが,K17では同色の三角形がどこかにできるのである.

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