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

３，辺彩色

　　グラフGの隣接する辺が異なる色になるように、グラフGの各辺に色をつけることを、Gの辺彩色といい、k個の色が使われているとき、それをk-辺彩色という。グラフGに対して、k-辺彩色が存在するときGはk-辺彩色可能であるという。Gがk-辺彩色可能であるが(k-1)-辺彩色可能でないとき、kをGの辺染色数といいχ1(G)で表す。

　　定理３・１

　　　完全グラフKpに対して、

　　　　χ1(Kp)=p(pが奇数)、p-1(pが偶数)

　　　である。

　　　(証明)

　　　　(1)pが偶数の場合、Kpは定理１・１より、p-1個の1-因子Fi(i=1、2、・・・、p-1)に分解できる。各因子Fiに色iを付ければ、Kpのp-1色による辺彩色が得られる。よって、χ1(Kp)≦p-1。一方、Kpの最大次数はp-1であるからχ1(Kp)≧p-1。したがって、χ1(Kp)=p-1となる。

　　　　(2)pが奇数の場合、Kpのp頂点を正p角形の頂点になるように配置し、正p角形の境界上のp個の辺をp色で塗る。そして、正p角形の内部の各辺を、その辺と平行な位置にある境界上の辺と同じ色を塗る。このようにして、χ1(Kp)≦pを得る。次に、Kpの辺彩色においては同色の辺が隣接せず、1本の辺が2頂点と接続していることより、(p-1)/2本の辺以下しか同じ色をつけることができない。ところで、Kpの辺の本数はp(p-1)/2本であるから、χ1(Kp)≧pが得られる。よって、χ1(Kp)=pとなる。(証明終わり)