完全グラフＫn（次数ｎ−１，辺数ｎ（ｎ−１）／２）に三角形は何個あるか？　これは（ｎ，３）で求めることができる．それでは・・・

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

【１】完全グラフの完全２部グラフ分解

　完全グラフ（たとえばＫ5，次数４，辺数１０）の辺集合をいくつかの完全２部グラフ（たとえばＫ3,3，辺数９）の辺集合に分解したい．

　たとえば，Ｋ6は５個の完全２部グラフに分解することができる．

　　Ｋ6＝Ｋ3,2＋Ｋ2,2＋Ｋ1,1＋Ｋ2,1＋Ｋ2,1

一般にＫnはｎ−１個の完全２部グラフに分解することは難しくない．

［Ｑ］もっとうまく分解することができるか？

［Ａ］ｎ−１個はbest possibleである．もっと少なくすることはできない．

［雑感］この結果をグラフの幾何学的安定性の判定に用いることはできるだろうか？

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

【２】完全グラフのペテルセングラフ被覆

　五角形の中に星形五角形が入ったことで有名なペテルセングラフは１０個の頂点からなる．頂点次数は３である．

　一方，完全グラフＫ10は頂点次数９，頂点数１０，辺数４５である．Ｋ10を３個のペテルセングラフで覆うことはできない．

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

【３】ムーアグラフ

　ムーアグラフとは内周２ｋ＋１，最小次数ｒ≧３，頂点数

　　１＋ｒ＋ｒ（ｒ−１）＋・・・＋ｒ（ｒ−１）^k-1

のグラフである．ｒ≧３，ｋ≧２の場合は

［１］ペテルセングラフ

［２］ホフマン・シングルトングラフ

［３］内周５，次数５７のグラフ

のいずれかである．

　ホフマン・シングルトングラフはペテルセングラフを貼り併せて得られる５０頂点，次数７，内周５のグラフである．

　内周５，次数５７のムーアグラフが存在するかしないかは証明されていないが，もし，内周５，最小次数ｒ≧３，頂点数

　　１＋ｒ＋ｒ（ｒ−１）＋・・・＋ｒ（ｒ−１）^k-1＝ｒ^2＋１

のムーアグラフが存在するならば，その次数ｒは３，７，５７であることは証明されている．

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