完全グラフK5やK3,3は平面グラフではないが、K5は２つの平面グラフに分解できる。このとき厚みが２であるという。E(K5)=2

完全グラフについてはn≠4　(mod6)ならE(Kn)=[(n+7)/6]であることが知られている。

また、n=4　(mod6)のとき

E(K4)=1

E(K10)=3

E(K22)=4

E(K28)=5

E(K34)=6

E(K40)=7

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

E(K9)=3つまり2つの平面表されない最小の完全グラフである

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

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

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

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

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

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