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

２、線グラフと全グラフ

　　グラフGにおいて、頂点集合E(G)を持ち、その中の2頂点は、G内の隣接する2辺であるとき、かつそのときに限って隣接するようなグラフをGの線グラフといいL(G)で表す。

　　グラフGの全グラフT(G)とは、集合V(G)⋃E(G)と1対1対応する頂点集合を持ち、T(G)の2頂点が隣接するのは対応するGの2つの要素(頂点と辺)が隣接しているか、接続しているとき、かつそのときに限るグラフのことである。

　　命題２・１

　　　T(Kp)=L(Kp+1)

　　　(証明)

　　　　完全グラフKpの性質より、L(Kp)もT(Kp)も正則グラフになる。r-正則グラフのサイズは握手補題より、rp/2になる。

　　　　完全グラフKpの位数pk=p、サイズqk=p(p-1)/2である。

　　　　よって、線グラフL(Kp)の位数pLはp(p-1)/2である。

　　　　全グラフT(Kp)の位数pTはpk+qk=p+p(p-1)/2=(p+1)p/2である。

　　　　線グラフL(Kp)の正則数rLを考える。p-1の完全グラフに頂点を1つ加えると、辺はp-1個加えることになる。p-1個の辺のうち1つに着目すると、加えた辺p-2個と元々あるグラフの1個の頂点に接続されているp-2個の辺と隣接している。よって、rL=2(p-2)である。

　　　　全グラフT(Kp)の正則数rTを考える。p-1の完全グラフに頂点を1つ加えると、辺はp-1個加えることになる。加えた頂点1つに着目すると、接続されている辺はp-1個、隣接されている頂点はp-1個で、2(p-1)である。加えた辺1つに着目すると、隣接されている辺は2(p-2)個、接続されている頂点は2個で、2(p-2)+2=2(p-1)である。よって、rT=2(p-1)である。

　　　　完全グラフKp+1の線グラフL(Kp+1)について考える。

　　　　Kp+1の位数pk=p+1、サイズqk=(p+1)p/2であるから、L(Kp+1)の位数pLは(p+1)p/2、L(Kp+1)は2(p+1-2)=2(p-1)の正則グラフである。これは、T(Kp)と同形である。よって、T(Kp)=L(Kp+1)である。(証明終わり)