完全グラフK4と同型な部分グラフをもたないグラフを考える。

その辺をどう塗る分けても同色の三角形が存在するようなものの、頂点数は

１０^10^10^10^10^10

以上である

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

　黄金比は正五角形と密接な関係にある．正五角形に対角線を書き入れると星形五角形できるが，この手順を繰り返すと，正五角形と星形五角形が少しずつ縮小しながら無限に入れ子状になった図形を作ることができる．正五角形に対角線を描き入れると星形五角形（ソロモンの星）ができるが，正五角形と星形五角形の入れ子はペンタグラムと呼ばれる．この図形が４次元正単体の２次元投影図であることを知っている人は少ないだろう．

　正五角形にすべての対角線を書き入れたグラフがＫ5である．正ｎ角形にすべての対角線を書き入れたグラフがＫnである．完全グラフＫnの頂点次数はｎ−１，辺数はｎ（ｎ−１）／２）である．

［Ｑ］Ｋnに三角形は何個あるか？

［Ａ］これはnＣ3で求めることができる．

　それでは・・・

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

　Ｋ5の正五角形を赤線で，星形五角形を青線で結ぶ．この図形には点をつなぐ線がすべて赤かすべて青の三角形は存在しない．

　しかし，Ｋ6のすべての２頂点間を２色の線で結ぶと，点をつなぐ線がすべて赤かすべて青の三角形ができる．

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

　　Ｎ（１）＝２，Ｎ（２）＝５，Ｎ（３）＝１６

　　Ｎ（ｑ）≦Σｑ！１／ｋ！

であるが，エルデシュは

　　Ｎ（ｑ）＝ｑ！Σ１／ｋ！

と予想している．これによると，Ｎ（４）＝６５であるが，Ｋ65に対する良い４配色は見いだされていない．

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