面の彩色数
この章ではグラフの閉曲面への埋め込みについて考察していく。すなわち、グラフが種数p の閉曲面に埋め込まれるための必要条件を調べていく。これにより1章のグラフの彩色数の 評価とあわせて、閉曲面の最小彩色数を調べることができるのである。
まず準備として境界つき多面体について考察する。
3．1 境界つき多面体
定義3．1境界つき多面体とは、以下のような方法で同一視されたものである。
1．有限個の多角形が与えられて、その多角形の辺の集合の真部分集合Dを考える。この 時、Dの要素の数は偶数になるようにする。
a同じ数字が2同ずつ表れるように、刀のすべての辺に番号付けをする。番号のかわり に記号を用いることもある。
3，定義2．2で行った、多角形の辺の向き付けと同じ方法でDのすべての辺に向き付け をする。
4．同じ番号の辺を、向きが合うように貼り合わせる。この貼り合わせについても、多面 体の構成で行った辺の貼り合わせと同じ方法で同一視するものとする。
また、多角形の辺でDに属さないない辺、すなわち番号付けも、向き付けもされていな い辺のことを、境界つき多面体の境界辺という。
定義3．1の1から、塊界つき多面体には少なくとも1つの境界辺が存在することが分かる。
境界つき多面体の境界辺と、少なくとも1本の境界辺に隣接している頂点をあわせたも のは、擬グラフの形になっている。このグラフを境界付き多面体の境界擬グラフという。こ の境界擬グラフの頂点の次数には次のような性質があり、いくつかのサイクルになっている。
定理3．2境界擬グラフの頂点の次数は、すべて2である。
証明 境界擬グラフの、任意の頂点を oとする。
1． oが、同一視する前の多角形の2本の境界辺に隣接しているならば、この2本の辺は、
境界つき多面体を構成する同一視において、貼り合う辺がないので、Uoに、貼り合う 頂点もなく、新たに隣接する辺はない。よって次数は2である。
2． oが、同一視する前の多角形の1本の境界辺eoに隣接しているならば、もう1本の隣…
接している辺には番号付けがされている。この辺を、e1と表わす。ε1と貼り合わされ る、もう1本の辺elについて、ηoと、貼り合わされる方の頂点を 1とする。 1が、隣 接しているもう1本の辺e2が、境界辺ならば、これに貼り合う辺はもうない。ε2が、
境界辺でないならば、e2には番号付けがされている。 e2とおなじ番号が付されている 辺があるはずであるからそれを4とする。辺e1のときと同様、略に隣接する頂点の うち、 、と、貼り合わされる方の頂点をび2とし、 2に隣接しているもう1本の辺が、
境界辺なら操作を終え、境界辺でないなら、同様の操作を繰り返す。この操作をでき るだけ繰り返せば、どこかで、境界辺に行き着く。この操作が頂点砺およびそれに隣 接する境界辺e。＋1で終わったとする。e。がeoと（向きは違うかもしれないが）同じ辺 になることもあることに注意する。
このとき、多面体を構成する同一視を行うと、ηo，…，砺は1つの頂点になり、その頂 点に隣接している番号付けされていない辺はεoとθ。＋1の2本、または1本の輪だけに なる。よって、境界擬グラフにおける、頂点ηoの次数は2である。
蜜
また、境界つき多面体のオイラー数も定義しておく。
定義3．3Tは境界つき多面体で同一視を行った後の境界つき多面体の頂点の数をβo、境界 辺を含めて辺の数をβ1、面の数をβ2としたとき、Tのオイラー数E（T）を、
Eの＝β。一β、＋β2 で定義する。
境界つき多面体のオイラー数には、次のような特徴がある。
定理3．4Tが連結な境界つき多面体ならば、オイラー数は1以下になる。
証明 定理3．2より、7の境界擬グラフβのすべての頂点の次数は2である。よってβは、
1つ以上の閉じた道からなる。閉じた道をω1，ω2，…，臨色＞0）とし、その道の長さをそれ ぞれ」1，12，…論とする。
新たな多角形、11角形、Z2角形、…為角形を用意し、 Z1角形をω1に、多角形の辺と道 の辺がちょうど貼り合うように同一視する。同様の操作をち角形、…嘉角形についても行
う。すると、Tに11角形、ち角形、…為角形を貼りあわせたものは、多面体になる。この 多面体をΣとする。Tは連結であったので、それに多角形を貼り合わせたΣも連結である。
Σは、7にた個の面を加えた物であるから、頂点数はβ0、辺の数はβ1、面の数はβ2＋ん となり、また、連結な多面体のオイラー数は、2以下であることから、
E（Σ） ＝ βo一β1＋β2＋た
＝ E（T）十た≦2 々は、1以上であることからE（7）≦1がいえた。
■
定理3．4で等号が成立する、すなわちTのオイラー数が1になるのはE（Σ）＝2，ん＝1 のときだけである。このことから次の定理が導かれる。
系3．5Tは、連結な境界つき多面体でTのオイラー数が1であれば、その境界辺は1つの 閉じた道になっており、境界辺と1つの多角形を同一視することによって球面が得られる。
3．2 グラフの閉曲面への埋め込み
グラフはもともとどの頂点が隣接しているかという、組み合わせ論的なものであるが、
隣…接する頂点に辺を張り合わせることにより位相空間と考えることもできる。位相空間とし て考えたグラフを閉曲面に埋め込めるための必要条件を考えたい。
埋め込みを行う準備といくつかの定義と定理を紹介する。
σをグラフとし、V（σ）＝｛ 1，η2，…，u。｝とする。ここで、次のような位相空間 γ（G）H（E（σ）×1）
を考える。ここでy（σ），E（G）は離散位相の空間、∫は［0，1］⊂Rである。 e∈一E（G）に対し て、eが、物，uゴ（kのに隣接しているならば、（e，0）〜陽，（ε，1）〜％という同値関係を考え ると、レ（のH（E（の×∫）／〜でσを、位相空間と考えることができる。この位相空間も（1 で表わすこととする。これを使ってグラフの埋め込みは、次のように定義する。
定義3．63は閉曲面で、σをグラフとする。σが3に埋め込み可とは、Gを位相空間と考 えて、Gから5への連続で単射な包含写像があることとする。
グラフが閉曲面に埋め込めるということは、グラフを閉曲面の上に描くことができるこ とと考えられる。
また次の定理は認めて用いることにする。
定理3．75は閉曲面で、Gをグラフとする。 Gが3に埋め込み可であれば、5と同相なあ る多面体Σが存在し、Σの辺と頂点で構成される擬グラフΣを考えると、σは、Σに、部分 グラフとして埋め込める。
この定理から、グラフの多面体への埋め込みは次のように定義できる。
定義3．8グラフGが多面体Σに埋め込み可とは、σがΣの部分グラフになっていることと
定義する。
これによりグラフの閉曲面への埋め込みは、閉曲面と同相な多面体への埋め込みで考えてい くことができる。
グラフが、閉曲面5に埋め込まれるとき、閉曲面3のオイラー数を使った次の不等式が
成り立つ。
定理3．9単純グラフGが、連結な閉曲面5に埋め込み可で、G≠K2ならば、α1，αoを、そ れぞれグラフの辺数、頂点数、E伺を閉曲面のオイラー数として、
α1≦3αo−3五1（5）
が成り立つ。
証明 グラフGが、閉曲面5に埋め込み可なので、閉曲面5と同相な多面体Σが存在 し、Gは、Σにも埋め込み可である。σをΣに埋め込んだとして、Σを多角形から構成する 際、Gの辺については貼り合わせを行わずに同一視したものをΣ とする。Σ の連結成分を、
処，乃，…，男とすれば、各ZはGの辺を境界辺とする連結な塊界つき多面体となる。αo，α1 をそれぞれGの頂点数、辺数、βo，β1，β2をΣの頂点数、辺数、面数、β乙，β｛，β1（1≦2≦オ）
を、男の頂点数、辺数、面数とする。次のような3つの和を考え、
オ オ せ
Σβ6，Σβ｛，Σβ1
ゴ＝1 ぜニ1 ぎ＝1
これら3つの和とβo，β1，β2との差を調べる。
す
まずΣβ1で重複して数えられるのは、σの頂点αで、定理3．2より各頂点αはそ
2＝1
オ
の次数回だけ数えられる・また・Σβ｛で｝ま・Gの辺は2回数えられる・よって次の等式が とユ
得られる。y（G）＝｛α1，α2，…，α尋とすると、
オ ん
β・一Σβ1一Σ・・1（αゴ）＋α・
伽1 舛1 オ
β1＝Σβトα1 歪＝1
オ
β・一Σβ1 唇＝1 ん
定理1．14より、Σval（α∂＝2α1なので、
ゴ＝1
E（Σ） ＝ β0一β1十β2 オ
一Σ（β1一β1＋β1）一2α・＋α・＋α・
撃
一ΣE⑳一α・＋α・
＝1
定理3．4より、玖Z）≦1であるから、
玖Σ）≦オーα・＋α・
次に、各境界つき多面体男に境界辺が3つ以上あることを示そう。
1．境界辺が長さ1のサイクルになっているとき、σに輪があることになるのでσが単純 グラフではない擬グラフになり矛盾。
2．境界辺が長さ2のサイクルで、2辺が違う番号付けになっているとき、Gに平行があ ることになるのでσが単純グラフではない擬グラフになり矛盾。
3，境界辺が長さ2のサイクルで、2辺が同じ番号付けで、2辺の始点同士と終点同士が 同じとき、もしZに他に境界辺がなければ、この辺の貼り合わせでzがΣの連結成 分になり、Σは連結であったから、孟＝1すなわちGで切り離した境界つき多面体の連 結成分は一つになり、上記の境界辺がGの干すべてになるからσはん2となり、仮定 に矛盾するよって長さ2の境界辺以外にも境界辺があるので境界辺は3つ以上ある。
4．境界辺が長さ2のサイクルで、2辺が同じ番号付けで、2辺の始点同士と終点同士が 同じではないとき、この辺の貼り合わせでこの2辺の始点、終点が同一視され、この 辺が輪を作るのでσが単純グラフではない擬グラフになり矛盾。
以上により、各境界つき多面体の境界辺の個数は、少なくとも3以上であることがわかる。
またσの辺はそれぞれ境界つき多面体の2つの境界辺となっているので3孟≦2α、である。
よって、
3E（Σ）≦3オー3α、＋3α。
≦ 2α1−3α1十3αo ≦ 3αo一α1
冒
3．3 閉曲面の最小彩色数と、且eawoodの不等式
閉曲面の最小彩色数を定義しておく。
定義3．10θを閉曲面とし、θの最小彩色数X（3）を以下のように定義する。θに埋め込み可 なグラフの最小彩色数の上限をx（5）とおく。
すなわちx（5）とは、もしそれが有限であれば閉曲面に埋め込むことのできるあらゆるグラ フを彩色することのできる色数のうち最小のものである。これで、定理3．11を証明する準備 が整った。閉曲面の最小彩色数は有限で、Heawoodの不等式と呼ばれる次の式で上から絞り 込むことができる。
定理3．11閉曲面3の最小彩色数は、E＜2のとき次の式で上から絞りこむことができる。
x（θ）≦
7＋4
P『24E］ここで［ ］は、ガウス記号を表わす。