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

　完全グラフ（たとえばＫ5，次数４，辺数１０）の辺集合をいくつかの完全２部グラフ（たとえばＫ3,3，辺数９）の辺集合に分解したい．たとえば，Ｋ6は５個の完全２部グラフに分解することができる．

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

一般にＫnをｎ−１個の完全２部グラフに分解することは難しくない．それでは，もっとうまく分解することができるかというと，ｎ−１個はbest possibleであって，これ以上少なくすることはできないのである．

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

【２】２部グラフによる完全グラフの被覆

2部グラフの族が完全グラフがＫnのすべての辺を覆うと仮定する。

このとき、これらの２部グラフの頂点を合わせると少なくともnlogn/log2個になる。

もっと正確にいうとn=2^k+l<2^(k+1)ならば、この最小値はnk+2lである。

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