完全グラフの問題

完全グラフＫnはｎ個の点のすべての２点を連結させてできるグラフである．したがって，完全グラフＫnの頂点数はｎ，頂点次数はｎ−１，辺数は（ｎ−１）／２となる．完全グラフＫnに三角形は何個あるか？　これはnＣ3で簡単に求めることができる．それでは・・・

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

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

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

　色を３色に増やす．Ｋ16は同色の三角形が存在しないように配色することができるが，Ｋ17では同色の三角形がどこかにできるのである．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝