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

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

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

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

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