四色問題
２年Ａ組

森田倖規

２年Ｂ組

佐藤奨

指導教諭

川口慎二

１．要約
サイエンス研究会数学班２年生は、地図の塗り分けを起源とする「四色問題」について学習している。その理解のために、グラフ理論に関する参考文献[1]を輪読しながら、基本事項の習得を行っている。本稿では、グラフの基本的な性質や用語の用意をしながら、四色問題に関する事実について紹介する。
キーワード

四色定理、グラフ、地図、次数、オイラーグラフ、単純グラフ、彩色可能性、双対性、面彩色、点彩色、辺彩色、彩色指数２．研究の背景と目的けを考えるときには、「平面グラフ」の考社会の授業で地図を色分けした経験がえ方が役に立つ。

あるだろう。地図の塗り分けについては、

本稿では、グラフの考え方を紹介すると「地図の隣り合った国を異なる色で塗ともに、地図の彩色とグラフの彩色の関係り分けるためには何色あれば十分なのを考察したい。また、四色定理は、かなりか」という問題が数学の問題としてあり、高度な数学の知識を必要とするため、まずこれに対しては、４色あれば十分であるは２色による彩色ができるためには、グラという結論である四色定理(four-colorフがどのような条件を満たせばよいのかtheorem)が知られている。

について学習した。

実際に、図１のように、日本地図において隣り合った都道府県を４色で塗り分けることができる。このような地図の塗り分

図１

日本地図の４色による塗り分け

３．研究内容
３－１．グラフとは
図２のように、有限個の点を線でつないだ図形を(平面)グラフ(graph)といい、この有限個の点を頂点(vertex)、つないだ線を辺(edge)という。また、各頂点に出入りしている辺の本数をその頂点の次数(degree)という。例えば、図２のグラフの頂点 A, D の次数はそれぞれ 2, 5 である。
また、辺 p のように、出発点と終点が同じ頂点である辺をループ(loop)という。
グラフ内で一周できる道を閉路(cycle)という。例えば、図２のグラフを見てみると、A→B→C→D→A が閉路である。

図３ 単純グラフ

図４

図２

図３と同型なグラフ①平面グラフの例①平面グラフ G のどの２点も辺でつながれているとき、G は連結グラフ(connectedgraph)であるといい、連結グラフ G が、すべての辺を通って出発点に戻る歩道を含むとき、G をオイラーグラフ(Eulargraph)という。
また、２点を結ぶ辺が２本以上あるとき、その辺を多重辺(multiple edges)という。
ループや多重辺を含まないグラフを単純グラフ(simple graph)という。
３－２．オイラーの定理
図３のグラフは、図４や図５のようにも書き換えることができる。

図５ 図３と同型なグラフ②
逆に、図４，図５を図３に変形することもできるので、図３から図５はいずれも同型であることがいえる。ここで、２つのグラフが同型(equivalent)であるとは、２つのグラフにおいて、それぞれ対応する各頂点の次数が等しいときをいう。すなわち、グラフにおいては、頂点と頂点の結びつきは、方向や距離を考えず、単に各頂点がどの頂点と結びついているかという情報が重要なのである。
さらに、グラフGにおいて、同じ頂点を二度と通らない閉じた道をサイク ル(cycle)という。
サイクルをもたない、連結されたグラフを木(tree)という。また、少なくとも一つの辺をもった木において、一つの辺の終 点 で あ る 頂 点 を 吊 り 頂 点 (pendantvertex)という。
さて、グラフが一筆書きできる場合について考えよう。グラフが一筆書きできるとき、それぞれの頂点から出る辺と入る辺の数が等しい。ただし、始点（出発点）と終点（到着点）は除いて考える。
２つの頂点を除いた頂点の次数がそれぞれ偶数であるとき、このグラフは一筆書きできるといえる。そして、始点と終点が一致する場合には、その頂点の次数も偶数になるが、一致しなければその２つの頂点の次数はそれぞれ奇数となる。
以上のことは、オイラーの一筆書き定理という定理として知られている。
定理１(オイラーの一筆書き定理)

次数が奇数となる頂点が０個か２個であるグラフは、一筆書きができ、それ以外の場合は一筆書きできない。
［証明］
まずは、グラフGが一筆書きできるとき、Gの頂点のうち、次数が奇数であるものは０個か２個であることを示そう。
上述のように、グラフGが一筆書きできるとき、始点と終点以外の頂点vでは、vに入ってくる辺とvから出て行く辺の数が等しい。つまり、始点と終点の２つの頂点を除いた頂点の次数はすべて偶数である。そして、始点と終点が一致する場
合には、その２頂点の次数も偶数になるが、一致しなければその２頂点の次数はそれぞれ奇数となる。
次に、次数が奇数となる頂点が０個または２個であるグラフ G が一筆書きできることを証明しよう。この証明には、辺の数に関する帰納法を用いる。
(ⅰ) G は次数が奇数である頂点をもたない、即ち、G のすべての頂点の次数が偶数である場合について考える。
まず、辺の数が 0 のとき、即ち始点のみの場合は、明らかに一筆書きできる。

ここで、辺の数が k 本以下のグラフ(ただし、すべての頂点の次数は偶数である)が一筆書きできていると仮定する。
さて、(すべての頂点の次数が偶数であり、) k  1 本の辺からなるグラフ G について考えてみよう。このグラフ G は、始点と終点が一致するので、吊り頂点をもたない。よって、木ではないことがわかる。したがって、G にはサイクル（閉じた道）があることがわかる。ここで、このサイクルに属する辺を一時的にすべて取り除くとグラフはいくつかの部分(これを連結成分(component)という)に分けられる（図６参照）。
しかし、これらの部分は、一時的に取り除いたサイクルと共通の頂点をもっている。これらの共通する頂点は、サイクルの頂点でもあるため、もともとの次数より 2 だけ小さくなる。よって、もとのグラフ G からサイクルを除いてできる各部分は、すべての頂点の次数が偶数であり、辺の数は k 本以下である。

G
図６

グラフ G の連結成分

すると、帰納法の仮定により、これらの各成分は一筆書きできることがわかる。
したがって、サイクルを一周して、連結成分と共有する頂点に着いたとき、その成分を一筆でかくことで、次数が奇数の頂点が０個の場合は証明できる。
(ⅱ) G は次数が奇数である頂点を２つもつ場合について考える。
まず、始点と終点を含むグラフ上の辺をそれぞれ取り除く。すると奇数の次数をもつ頂点がなくなることがわかる。

k 色で彩色することができるとき、この地図は k ‐点彩色可能であるとする。
定理３
地図 G が 2‐彩色可能であるための必要十分条件は、G がオイラーグラフになることである。
図７ 次数が奇数である頂点を２個もつ場合
このグラフは(ⅰ)において議論した、次数が奇数である頂点をもたない、即ちすべての頂点の次数が偶数であるグラフになるので、あとは、(ⅰ)と同様に証明できる。
(ⅰ)，（ⅱ）より、次数が奇数となる頂点が０または２個であるグラフ G が一筆書きできる。
以上から、オイラーの一筆書き定理が証明された。(Q.E.D.)
上の定理から、一筆書きできるグラフのことを、オイラーグラフとも呼ぶので、定理１（オイラーの一筆書き定理）を言い換えると、次のような命題になる。

[証明]
G は 2 色で彩色できるはずだから、Gの各点 g に対して、 g を囲む面の個数は偶数でなくてはならない。したがって、各頂点の次数は偶数であるので、定理２(オイラーの定理)から、G がオイラーグラフであることが分かる。
逆に、G がオイラーグラフであると仮定する。G の面を彩色するために、任意に面 F を選んで、F を色１(例えば赤)で塗る。
F の中の点 x から、他の面 H の点 y へ行く線をかく。ただし、この線 xy はグラフG の頂点を通らないようにする。

定理２（オイラーの定理）
連結グラフＧがオイラーグラフである
ための必要十分条件は、Ｇのすべての頂点の次数が偶数になることである。
３－３．２色による彩色
まずは、簡単な 2‐彩色可能な地図の条件を見ていくことにする。以降、地 図(map)とは、すべての頂点の次数が 3 以上で、ループを含まない連結グラフと約束する。
地図の隣接している２つの面(辺を共有する２つの面)が同色にはならないようにk 色で彩色することができるとき、この地図は k ‐彩色可能( k -colorable)であると定義する。また、地図の隣接している２つの頂点が同色にはならないように、頂点を

図８ グラフの彩色
この線 xy が偶数本の G の辺と交わるとき、面 H を色１(赤)で、奇数本の辺と味割るときには、面 H を色２(例えば青)で彩色する。図８を見よ。
このように彩色してから、 xy のような２本の線からできる閉路を考えると、Gはオイラーグラフであることから、この閉路は G の偶数本の辺としか交差せず矛盾が起こることはない。(Q.E.D.)

３－４．地図の彩色とグラフの彩色
地図の彩色とグラフの彩色の関係をみるためには、双対性(duality)という考え方が必要である。平面グラフ G に対して、
グラフ G＊を次のように作る。
① G の各面 F から１点 x を選び、これを G＊の頂点とする。
② G の各辺 e にだけ交わるような線 fを引き、この e に接する２つの面内の点を結び、G＊の辺とする。
このとき、この新しいグラフ G＊を Gの(幾何学的)双対という。

G

図 10 グラフ G の点彩色

G＊G

G＊
図９

図 11 グラフ G の面彩色

グラフ G の幾何学的双対 G＊

定理４
G をループのない平面グラフとして、G を G の双対とする。このとき、G が k‐点彩色可能であるための必要十分条件は、G＊が k ‐彩色可能であることである。
＊[証明]
G をループのない平面グラフとして、その双対 G＊は地図であるとする。もし、G が k ‐点彩色できれば、G＊の各面にはG の点がちょうど１個ずつ含まれているので、その色で G＊の各面を彩色できる。
したがって、G＊は k ‐彩色可能である。
逆に、平面グラフ G の双対 G＊が k ‐彩色可能であるとする。G の各点は G＊のいずれかの面に含まれているので、その面で G の頂点を彩色できる。したがって、G は k ‐点彩色可能である。(Q.E.D.)

最後に、地図の彩色とグラフの彩色の関係について述べたい。平面グラフの四色定理とは、「すべての平面グラフは 4‐点彩色可能である」というものである。
定理２から、四色定理の同値性が示される。
定理５
地図に関する四色定理は平面グラフに関する四色定理と同値である。
[証明]
平面グラフ G は、ループを含まないものとする。その双対 G＊は地図であり、地図が 4‐彩色可能であるという仮定から、定理４から明らかに、グラフ G は 4‐点彩色可能である。
逆に、地図 G の双対 G＊を考える。このとき G＊は平面グラフであり、仮定から4‐点彩色可能である。したがって、G＊の双対 G は 4‐彩色可能である。(Q.E.D.)

３－４．辺彩色
３－３節では、地図の彩色(これを面彩色(face-coloring)ともいう)と、平面グラフの頂点彩色(vertex-coloring)を「双対」という考え方でつなげられることを学習した。ほかにも「辺彩色(edge-coloring)」という考え方がある。
グラフ G の隣接する辺は同じ色にならないように、グラフ G の辺を k 色で彩色できるとき、このグラフ G は k ‐辺彩色可能( k ‐colorable(e))であると定義する。
また、グラフ G が k －辺彩色可能である(0, 0)と表すことにする。このとき、Ｇの3－辺彩色は次のようにして得られる。
各辺 e が接する２つの面の色を mod 2で加えて得られる色によって辺 e を彩色すればよい。例えば、辺 e に接する２つの面が色αとγで彩色されているとき、(1, 0)＋(1, 1)＝(0, 1) (mod 2)

が、 (k  1) 辺彩色可能でないとき G の彩であるので e を  で彩色することになる。

色指数(chromatic index)は k であるといここで、各辺に接する２つの面の色は異なることから、  はこの辺彩色には現れない。そして隣接する２本の辺が同じ色を共有しないことも明らかである。(Q.E.D.)い、  (G )  k と表すことにする。G の最大次数を  とすると、  (G ) ≧  であることは自明である。図 12 のグラフ G に対しては、  (G )  4 である。

［証明］
G の面に関する 4－彩色が与えられていると仮定して、そこで用いられる色を順に  ＝(1, 0)，  =(0, 1)， ＝(1, 1)， ＝

定理６は逆も成立することが知られているが、今回は証明を省略する。

４．今後の課題
本年度は、参考文献[1]を輪読し、地図の塗り分けをきっかけに、グラフの彩色について考察した。グラフ理論にはさらに深い内容があるため、今後も引き続き、学習・研究を継続したい。

図 12

 (G )  4 であるグラフ G

次の定理６は、３次(すべての点の次数が３以下)の単純グラフＧの彩色指数と四色定理の関係を示している。
定理６
四色定理が成り立つならば、どのような３次の地図 G に対しても、  (G )  3 が成り立つ。

５．参考文献[1]「グラフ理論入門」, R. J. ウィルソン著，西関隆夫、西関裕子共訳，
近代科学社 (2001)
６．謝辞
顧問の川口先生には、わからない部分を説明してもらい、公開研究会でのポスターや本稿についても、いろいろなアドバイスをいただきました。ありがとうございました。