■完全グラフの完全2部グラフ分解(その1)

【1】完全グラフの完全2部グラフ分解

 完全グラフ(たとえばK5,次数4,辺数10)の辺集合をいくつかの完全2部グラフ(たとえばK3,3,辺数9)の辺集合に分解したい.たとえば,K6は5個の完全2部グラフに分解することができる.

  K6=K3,2+K2,2+K1,1+K2,1+K2,1

一般にKnをn−1個の完全2部グラフに分解することは難しくない.それでは,もっとうまく分解することができるかというと,n−1個はbest possibleであって,これ以上少なくすることはできないのである.

===================================