4．1 グラフのローテーション
グラフの閉曲面への埋め込みを構成するよい方法に、グラフのローテーションを利用 するものがある。グラフのローテーションから、グラフが埋め込み可な閉曲面を見つけ、そ れを用いて閉曲面の最小彩色数を下から評価していくことができる。
グラフのローテーションを次のように定める。
定義4．1グラフσで、σの頂点ηのローテーションとは、 に隣接しているすべての頂点 を円順列として書き並べてできた列ρ。であるとする。円順列と巡回置換には1対1対応が あるのでこれを巡回置換であると考えてもよい。
そしてσのローテーションとは、σの各頂点でのローテーションの集まりρ＝｛ρ。｝と 定義する。
ローテーションを表記する場合、頂点の番号の後にピリオドを打ち、その後に隣接する頂点 の番号を書き並べる。例えば、次のグラフにおいて●の頂点についてはその周りの頂点を時 計回りに、○の頂点についてはその周りの頂点を反時計回りに並べた円順列のローテーショ
ンを対応させグラフのローテーションを与えたとする。
1 2
0
4 3
このローテーションは、
0． 1，2，3，4 1．4，0ラ2 2．0，3，1
3．204
， ，
4．301
， ，
と書き表わされる。以後ローテーションを図示する時は、上記の○、●を使った方法を用い る。つぎにローテーションから決まるサーキットと呼ばれる閉じた道を考える。
グラフσとそのローテーションρがあたえられているとする。このとき、ある隣接し たσの2つの頂点ηo，u1にたいして
＋1＝＝ρu盛（り2＿1）
により頂点の列 iσ＝0，1，2，3，…）がきまる。ただし、ここで頂点 ゴのローテーション 侮は巡回置換と考える。
命題4．2あるNがあって、任意の￠について物二η什Nとなる。
証明 定義4ユの操作を繰り返していくと、σの頂点数は有限個であるから、どこかで 妬＝㌦，賜＋1＝隔＋1となるη，m（η≠m）がある。ここでη＜mとおく。 Uπ，妬＋1で η叶2がきまるので、このとき 。＋2＝㌦＋2。これを繰り返せば任意の駁2≧η）に対して 物＝ 狂観覗となる。
また、ρによる置換は可逆であるので、
U臼＝ρ舜1＠歪＋1）
ともかける。よって 。， 。＋1で 。一1がきまると考えられるから π一1＝Um−1， 。一2＝ m−2と
なる。よってN＝m一ηとすれば定理は成り立つ。
圏
定義4．3グラフσでそのローテーションの一つをρとする。上記の定理から定義4．1を満た す点列物は周期的になることがわかる。その最小の周期をNとして、 o， 1， 2，…， N−1， o
と頂点をたどる閉じた道をサーキットという。サーキットの頂点数をサーキットの長さと
いう。
定義4．4グラフσでそのローテーションの一つρによってできたサーキットの長さがすべ て3になるときそのローテーションを特にトライアンギュラーローテーションという。
ローテーションの決め方によって、サーキットの数も変わってくる。
定義4．5グラフGでそのローテーションの1つをρとしたとき、α2（G，ρ）とは、ρによって できたGのサーキットの数とする。はじめの2頂点を決めるとサーキットが決まるので、辺
とその向きを決めるとその辺をその向きに通るサーキットが必ず1つ存在する。よってサー キット全体としては、全ての辺を2度つつ通る。
グラフとローテーションによるサーキットの数には、次のような定理がある。
定理4．6グラフσでそのローテーションの1つをρとする。また、σの辺εにたいして、
σ一εとはσから辺θを取り除いて得られるグラフとする。辺εが次数1の頂点に隣接して いないとき、次の式が成り立つ。
1α、（G，ρ）一α2（G一・，ρ ）1＝1
ただし、ローテーション〆は、η1→e← 2＠1≠u2）とした時、 u1，u2以外の頂点については ρ．に等しく、η1についてはρ。、の順列から 2を、η2についてはρ。、の順列から 1をそれぞ れ除いたものとする。
証明 σでεに隣接している2つの頂点を、η1，η2とする。G−eを考えるとき、多くとも 2つのサーキットにしか影響しない。εに向きを与え、始点を 1終点を 2とする。η1から U2向かう部分があるサーキットをα、 2から 1向かう部分があるサーキットをβ、とする。
1．α＝βのとき、つまりαとβがつながっていて1つのサーキットになっている場合は、
これが分かれて2つのサーキットとなる。
2．α≠βのとき、つまりαとβが2つのサーキットになっている場合は、つながって1 つのサーキットになる。よってどちらの場合もα2（G，ρ）とα2（G−e，ρ）の差は1なの で定理が成り立つ。
璽
4．2 向き付け可な閉曲面の最小彩色数の決定
次の定理によりグラフにローテーションが与えられた時、そのグラフが埋め込み可な多 面体を構成することができる。
定理4．7グラフGにローテーションρが与えられた時、次の条件を満たすような向き付け 可な多面体Σが存在する。
1．σがΣに埋め込まれる。
ゑΣの頂点数、辺数、面数をそれぞれα0（Σ），α1（Σ），α2（Σ）、またGの頂点数、辺数をそ れぞれαo（G），α1（G）とし、グラフσにローテーションρを与えた時にできるサーキッ トの数をα2（G，ρ）とする時、
α・（Σ）＝α。（G）
α・（Σ）＝α、（の α2（Σ）＝α2（G，ρ）
が成り立つ。
1
巴
η1∫
←
β
G
・・o2
→ り↑掴
G−e
2
α
→
η1 ．
β
←
G
． 2
一
｝↓G．e
↑％
7
証明 （σ，ρ）でできるサーキットを隅，鵬，…，鴨とする。Gのすべての辺に番号と向き を定める。すなわちE（G）＝｛1，2，…，m｝とし、このとき㎎をその辺の番号の列で表わす。
さらに、サーキットがたどる向きと辺の向きが一致する、一致しないに応じて番号に（＋1）
乗、（一1）乗の指数をつけて表わす。それを臓＝α1㌔穿）…α！l）とする。この時このサーキッ トを並べて、
1．・〜1），・〜1）デ・・，・≦P 2．・12），・12），…，・9）
（π） （π）
＠）
γ乙・ α1
，α2 ， ，αオη
としたものを記号表現として得られる多面体Σを考える。サーキット全体はすべての辺を2 度ずつ互いに逆の方向でたどるから、このΣは向き付け可な多面体になる。また実はこの多 面体は、各サーキットを境界とする多角形をGにサーキットに沿って貼り合わせたものに なっている。よって、Σの頂点数、辺数はσの頂点数、辺数に等しく、Σの忌数はサーキッ
トの数と等しくなる。
翼
特にローテーションがトライアンギュラーローテーションならば、この定理を使って、次の 系が成り立つ。
系4．8グラフσのトライアンギュラーローテーションρが存在する時、ある向き付け可な 多面体Σが存在し、σがΣに埋め込み可で、かつ
α1（Σ）＝3αo（Σ）一3E（Σ）
が成り立つ。
証明 前定理で構成した多面体Σは、向き付け可でσを埋め込み可であることは明らかで ある。また、前定理から
α。（Σ）＝α。（σ）
α1（Σ）＝α1（σ）
α、（Σ）＝α2（G，ρ）
が成り立つ。ここで、ρはトライアンギュラーローテーションであるので、サーキットの長 さはすべて3である。また、各辺はちょうど2回つつそれぞれ反対の方向でサーキットに表 われているから次の式が成り立つ。
3α2（σラρ）＝2α1（G）
また閉曲面のオイラー数は、
E（Σ）＝α0（Σ）一α1（Σ）十α2（Σ）
であるから2式より、
2
E（Σ）一α・（Σ）一α・（Σ）＋喜α・（σ）
よって
α、（Σ）＝3α。（Σ）一3E（Σ）
を得る。
墨
次に完全グラフK。のローテーションを考える。トライアンギュラーローテーションは、ど んなグラフにもあるとは限らない。実際、完全グラフK。のトライアンギュラーローテーショ ンの存在は、次の定理で限定される。
定理4．9完全グラフκ．にトライアンギュラーローテーションρがあればη≡0，3，4，7（mod12）
となる。
証明 κ。にトライアンギュラーローテーションがあるとすると、前定理と系よりκ。を埋 め込める多面体Σが、
α。（Σ）＝α。（K。）
α、（Σ）＝α、（一κ。）
α2（Σ）＝α2（κ。，ρ）
を満たして存在する。またこのとき、
α1（Σ）＝3αo（Σ）一3五1（Σ）
も成り立っており、α0（κ。）＝η＝α0（Σ），α1（κ。）＝禦1＝α1（Σ）を代入すれば次の式が 導かれる。
3E（Σ）一3・一禦 E（Σ）一一≒互
またΣの平地をpとしてE（Σ）＝2−2pより 一≒勉一2−2P
2P」一警＋12 γL2−7π十12 P＝ 12 れ ヨ れ P＝ 12
pの値は、明らかに整数であるので、η≡0，3，4，7（mo412）となる。
屠
一方で、一般に瓦がΣに埋め込まれる時、Σの画数は次の不等式を満たす。
定理4．10完全グラフ瓦が多面体Σに埋め込み可であれば、pをΣの種数として、
P≧（ 31穿一4）］
が成り立つ。
証明
1・一2のとき・［η三一41一・なので明らかに成り立つ・
2．η≠2のとき、定理3．9より
α、（一κ。）≦3α。（一κ。）一3E（Σ）
であるから、
3E（Σ）≦3・一禦 E（Σ）≦一学
またE（Σ）瓢2−2pより
2−2P≦一≒璽
2P≧η2一警＋12 P≧π≒雪＋12
P≧（7乙一3）（γゐ一4 12）
pの値は明らかに整数であるので、
P≧ （η一3）（γτ一4）
12
置
この2つの定理から、完全グラフにトライアンギュラーローテーションがあれば定理4．7 系4。8により、最小種数の埋め込みが得られる事がわかる。実は、次の2つの定理が知られ
ている。
定理4．11η≧3とするとき完全グラフ凡に対して、K。が埋め込み可な多面体Σが存在し、
（γz−3）（η一4）
P＝
12 が成り立つ。
定理4．12η≡0，3，4，7（mo412）のとき、一κ．にはトライアンギュラーローテーションがある。
これらの証明は、ηを12で割った剰余による場合分けで証明され、大変長いものとなる。
しかし、それぞれの場合分けについての証明は本質的に似たような手法で証明されている。
本論文では次節でそれらの場合分けのうち、比較的証明が容易な定理4．12のη≡7（mo412）
の場合を証明する。
また定理4．11、4．12を使うと、次の定理が証明される。
定理4．13向き付け可な閉曲面θの最小彩色数は、E＜2のとき 7十 49−24E
x（3）＝
2
となる。
証明 Kηが5pに埋め込み可で、3p−1に埋め込み不可のとき、このpの値をッ（κので表わ す事とする。閉曲面5の種数をgとし、πを次の条件を満たす最大の整数とする。
（η一3）（γ乙一4）
ッ（一κの＝
≦9 12
このときg〈7（κ。÷、）であるから、
9〈（π一211η一3）
12g＜（η一2）（η一3）
0＜γz2−5γL十6−129
0＜（・一5＋、＋489）（・一5一、＋489）
となる。ここで、E＜2であるので9≧1、ηは整数より（ 5−V圃γL− 2）＞0がいえる。よっ て（ 5＋v幅γz− 2）＞0となる。変形して
7一＞丁函 一1 η＞
2
を得る。瓦が、3に埋め込み可であるから、x（5）≧ηよって 7一・孚亜一1くx（5）≦7−4画
x（5）一［7＋許48gl E！＝2−2gより x（θ）一「7＋辱璽］
■
これで、Heawoodの不等式は、実は等号が成り立つことが証明された。よって球面以外の向 き付け可な閉曲面の最小彩色数が決定されたことになる。
4．3 トライアンギュラーローテーションの存在
この節では実際にπ≡7（mo4！2）のとき、瓦のトライアンギュラーローーテーションを構i 成する方法について述べる。まず、ローテーションがトライアンギュラーであるための条件 について考察する。
定義4．14グラフのローテーションに次のような規則性があったとき、そのローテーション は、ルールムを満たしているという。
●ある頂点ゴのローテーションカ㍉．…，ブ汐，…という列であれば、頂点乃のローテー ションはん．…鵡ブ，…という列になる。
定理4．15グラフGでルールムを満たしているローテーションは、トライアンギュラーロー テーションである。
証明 σの隣接する頂点ゼ，ブからはじまるサーキットを考える。ゼ，ブは隣接しているので頂 点ブのローテーションを表わす列は必ず￠を含む。σの頂点ブのローテーションが、
ゴ．…，￠，ん，…
とすると、ルールムより、頂点たのローテーションは た．…，ブ，2ッ…
となっている。さらに頂点ゴのローテーションは、やはりルールムより、
乞．…，んラゴ，…
となっている。よってサーキットを考えると、￠飴という閉じた道になり長さは3である。
咀