完全グラフと全彩色予想①

(注意)完全グラフと全彩色予想の内容や定理の証明は「グラフ理論序説」からお借りしている部分が多いです。

１，因子分解

　　グラフHがグラフGの部分グラフであるとは、Hが

　　　V(H)がV(G)の部分集合　かつ　E(H)がE(G)の部分集合

　　を満たすグラフのことである。特に、V(H)=V(G)のとき、HをGの全域部分グラフという。グラフGの全域部分グラフのうち、木であるものを全域木という。

　　各頂点の次数(頂点に接続する辺の数)がすべて等しいグラフを正則グラフといい、各頂点の次数がkの正則グラフをk-正則グラフという。

　　グラフGの空でない全域部分グラフを因子といい、Gのr-正則な因子をr-因子という。

　　グラフGが因子の辺和として表されるとき、この和をGの因子分解という。すなわち、グラフGの因子Fi(i=1、2、・・・、n)があって、

　　　V(Fi)=V(G)、E(Fi)≠0　(i=1、2、・・・、n)

　　　E(Fi)⋂E(Fj)=0　(i≠j、i、j=1、2、・・・、n)

　　　⋃{n,i=1}E(Fi)=E(G)

　　が成り立っているとき、{F1、F2、・・・、Fn}をグラフGの因子分解という。特に、F1、F2、・・・、Fnがすべてr-因子のとき、r-因子分解という。Gにr-因子分解があるとき、Gはr-因子分解可能という。

　　位数pのグラフで、そのどの2頂点も隣接しているとき、位数pの完全グラフといい、Kpであらわす。完全グラフKpは(p-1)-正則グラフであり、サイズはp(p-1)/2である。

　　定理１・１

　　　完全グラフK2pは1-因子分解可能である。

　　　(証明)

　　　　p=1のとき明らかであるから、P≧2と仮定してよい。

　　　　K2pの点をv1、v2、・・・、v2pとし、正(2p-1)角形上の点に、反時計回りにv1、v2、・・・、v2p-1を配置する。正(2p-1)角形の中心をv2pとする。すべての頂点対を辺で結べばK2pとなっている。

　　　　このとき、K2pの各1-因子Fi(i=1、2、・・・、2p-1)を、v2pvi及びそれに垂直な辺全体と定義する。そうすると、FiとFj(i≠j)はE(Fi)⋂E(Fj)=0で、F1、F2、・・・、F2p-1の返和がK2pとなっている。

　　　　よって、{Fi}(i=1、2、・・・、2p-1)によるK2pの1-因子分解が得られた。(証明終わり)