極大平面的グラフの頂点彩色と四色問題②

２、木

　閉路のない連結なグラフを木と呼ぶ。

　定理２・１

　　木において、位数をp、サイズをqとすると、

　　　p=q+1

　　が成り立つ。

　　(証明)数学的帰納法で証明する。

　　　①位数p=1のとき、サイズq=0である。

　　　　q≧2とすると、p=2のとき、q=1により式が成り立つ。

　　　②位数がp-1以下のすべての木について定理が成り立つと仮定する。

　　　　木Tが1つの辺を取り除くと、2つの木T1、T2に分かれるとする。

　　　　このとき、木T1、T2の位数をp1、p2、サイズをq1、q2とすると、帰納法の仮定より、

　　　　　p1=q1+1、p2=q2+1

　　　　が成り立つ。木Tについては

　　　　　p=p1+p2、q=q1+q2+1

　　　　が成り立ち、

　　　　　p=p1+p2=(q1+1)+(q2+1)=(q1+q2+1)+1=q+1

　　　　よって、公式が成り立つ。(証明終わり)

３，平面的グラフ

　グラフGで、どの2辺もその端点以外では交差しないよう幾何学的に平面上に描くことができたとき、Gを平面的グラフと呼ぶ。

　平面的でないグラフを非平面的グラフと呼ぶ。

　平面的グラフを平面への埋め込み(Gに同形なグラフを平面上に描くこと)を行って、平面上にどの辺も交差しないように描かれた平面的グラフを平面グラフと呼ぶ。

　平面グラフを、有限個の領域に分ける。これらの領域をそれぞれ平面グラフの面と呼ぶ。

　各平面グラフは1つの有界ではない面をもち、これを無限面という。その他の面は有限面である。

　定理３・１(オイラーの公式)

　　Gを連結平面グラフとする。Gの位数をp、サイズをq、面の個数をrとすれば、

　　　p-q+r=2

　　が成り立つ。

　　(証明)Gの辺の数に関しての数学的帰納法で証明する。

　　　①q=0のとき、Gは連結であるのでp=1、無限面しかないので、r=1である。

　　　　したがって、p-q+r=1-0+1=2。よって、公式は成り立つ。

　　　②q-1本以下の辺を持つすべてのグラフGで公式が成り立つと仮定する。

　　　　いま、グラフGにはq本の辺があるとすると、もしGが木ならば、q=p-1であり、r=1であるから、

　　　　　p-q+r=p-(p-1)+1=2

　　　　で公式が成り立つ。

　　　　Gが木でない場合、Gの閉路に含まれる1つの辺をeとし、このeを取り除くと、面が1つ減る。

　　　　　p-(q-1)+r-1=p-q+r=2

　　　　となり、公式は成り立っている。(証明終わり)

　平面的グラフGにおいて隣接していない任意の2点に1つの辺を加えると、非平面的グラフになるとき、この平面的グラフGを極大平面的グラフと呼ぶ。

　系３・２

　　グラフGを位数p(p≧3)の極大平面的グラフとすると

　　　q=3p-6、r=2p-4

　　である。

　　(証明)

　　　グラフGの面の数をrとすると、極大平面的グラフの場合、すべての面が3つの辺からなっていて、しかも、どの辺も2つの面の境界をもつ。よって、

　　　　3r=2q

　　　である。この式をオイラーの公式とで面の数rを消去するとq=3p-6が導かれ、サイズを消去するとr=2p-4が導かれる。(証明終わり)