2016

有限数学第２

小関 健太

2016

本講義は，グラフ理論のいくつかの知識は既知と仮定する．基本的な内容は「有限数学 第一」の講義，またはグラフ理論の基礎的な教科書を参照のこと．

1

握手補題の応用

本稿では，多重辺およびループのない単純グラフのみを扱い，単にグラフとよぶ．グラ フ G とその頂点 x に対し，x に接続する辺の数を G での次数とよび，dG(x) で表す． 定理 1 (握手補題) G をグラフとすると，以下が成り立つ． ∑ x∈V (G) dG(x) = 2|E(G)|. 定理 2 (奇点定理) 任意のグラフは次数が奇数の頂点を偶数個持つ．

1.1

応用

1:

ランプパターン

n× m のマス目にランプが並んでいる．各マスのランプは，その位置のボタンを押す と on-off が切り替わる．(図 1 参照) 初期配置はすべてのランプが off で，全部のランプ を on にしたい．これができるマス目を反転可能 という． 図 1: ランプの on-off の例．(各回では×のマスのボタンを押しており，斜線のマスのラ ンプが on になっている．) これをグラフの問題へと変換する．すなわち，グラフ G の各頂点にランプがあり，一 つの頂点 v のボタンを押すと，v とその近傍 N (v) にあるすべてのランプの on-off が切り 替わる．グラフが反転可能とは，マス目の場合と同様の意味で使う．なお，次の性質が， グラフ G が反転可能であるための必要十分条件である． 次を満たす頂点集合 S ⊆ V (G) が存在する． |N(v) ∩ S| が { 奇数 v ̸∈ S のとき， 偶数 v ∈ S のとき． 定理 3 任意のグラフ G はある操作で反転可能である． 証明． _{|G| に関する帰納法．|G| = 1 ならば OK．(その頂点のボタンを押せば良い．)} よって，_{|G| ≥ 2 とする．} 主張 3.1 任意の頂点 u に対し，「ある操作 Su で u 以外の頂点が反転し u は反転しない」 としてよい．

証明． 帰納法の仮定より，G− u はある操作 Su で全頂点が反転する．Su を G に行っ たとき，もし u も反転するならば，操作 Su で G は反転可能となり証明が終了する．し たがって，Su では u は反転しない，としてよい． □ 主張 3.2 任意の頂点 u, v に対し (u ̸= v)「ある操作 Su,v で u と v のみ反転する」とし てよい． 証明． 主張 3.1 にある操作 Su と Sv を考える．操作 Su,v を，G で Su の後に Sv を行 うもの，と定義すると，これで u と v のみ反転する． □ ここで，まず G の全頂点のボタンを一度ずつ押す．このとき，各頂点 v で v の次数が 奇数，かつそのときに限り v のランプは off となる．ここで奇点定理より， {v ∈ V (G) : dG(v) は奇数} は偶数個の頂点よりなるので，それを v1, v2, . . . , v2k と書くことができる．主張 3.2 より， 操作 Sv1,v2, Sv3,v4, . . . , Sv2k−1,v2k を一度ずつ行うことで，全頂点が on となる． □ 演習 1 3_{× 3 のタイルの場合に，全頂点の on-off を反転させよ．また，3 × 4 ではどうか?} 演習 2 初期配置が「1 頂点のみが on で他はすべて off」のとき，すべての頂点を同時に on にはできない場合がある．そのような例を見つけよ．

1.2

応用

2:

山登り

A，B の二人が 1 本道の山道の両端のそれぞれにおり，その標高はどちらも 0m とする． ここで， A と B のいる地点の標高は常に等しい という条件を満たしながら二人が移動する．(図 2 を参照．特に，2 番目から 3 番目にお いて B は後戻りしていることに注意せよ．) A B A B A B A B 図 2: A, B の移動の例． 定理 4 標高がマイナスの地点は存在しないとすると，A, B は出会うことができる．

証明． 簡単のため，山道はすべて階段であり高さがそろっているとする．さらに，この 階段を左から順に 0, 1, 2, . . . , ℓ と名前をつけておく．A が 0 番目の段に，B が ℓ 番目の 段にそれぞれいる場合がスタートである．ここで S ={(i, j) : 0 ≤ i ≤ j ≤ ℓ, i 番目の段と j 番目の段は高さが等しい} という集合 _{S を頂点集合とし，S の二つの元 (i, j) と (i}′, j′) に対し，i′ = i± 1 かつ j′ = j± 1 であるときに辺で結んだグラフ G を考える．すなわち，S は A と B がいる可 能性のある位置のペアの集合であり，A が i 番目の段に B が j 番目の段にそれぞれいる 場合に，一回の移動で A が i′ _{番目の段に B が j}′ _{番目に移れるとき，(i, j) と (i}′_{, j}′_{) を} 辺で結んでいる． このとき，次の主張が成り立つ．(証明は演習問題とする．) 主張 4.1 (i) 初期配置 (0, ℓ)∈ S の G での次数は 1 である．

(ii) (i, j)∈ S − {(0, ℓ)} に対し，i ̸= j ならば (i, j) の G での次数は偶数である．

したがって，主張 4.1 (i) より頂点 (0, ℓ) の次数は奇数であり，G において (0, ℓ) を含む 連結成分 C に対し奇点定理を用いると，C に (0, ℓ) 以外の次数が奇数の頂点 (i, j) が存 在することがわかる．主張 4.1 (ii) より i = j である．C は連結成分なので，頂点 (0, ℓ) から 頂点 (i, i) への道が存在し，その順に状態を遷移させることで i 番目の段で A と B が会うことができる． _□ 演習 3 主張 4.1 を示せ． 演習 4 定理 4 において “標高がマイナスの地点は存在しないとする” という条件を仮定 しないと反例が存在するが，これを示せ．

1.3

応用

3:

整数長の辺を持つ長方形への分割

次の定理を奇点定理を使って証明しよう． 定理 5 長方形 ABCD の内部を，小長方形へ分割する．(図 3 参照) このとき，すべての 小長方形で縦か横の長さが整数ならば，もとの長方形 ABCD でも縦か横の長さが整数と なる． 証明． 長方形の頂点 A, B, C, D を，A を原点に，B を x 軸上に，D を y 軸上にそれ ぞれ配置する．このとき，次のグラフ G を考える．各小長方形の頂点と中心の集合を G の頂点集合とし，次のように辺集合を定義する：各小長方形の頂点 (x, y) に対し，x ま たは y が整数である，かつそのときに限り頂点 (x, y) とその小長方形の中心を辺で結ぶ． 例えば，4 頂点の座標が (1, 1/2), (√2, 1/2), (√2, 5/2) および (1, 5/2) の小長方形の場合を 図 4 に示す． 以下，このグラフ G での次数を考えることで頂点 B の x 座標または頂点 D の y 座標 が整数であることを示せる． _□

D A B C 図 3: 長方形の小長方形への分割 (1, 1/2) (1, 5/2) (√2, 1/2) (√2, 5/2) 図 4: 小長方形の例と G の辺 演習 5 各頂点の G での次数を考えることで，定理 5 の証明を完結せよ． 演習 6 定理 5 は 3 次元以上に拡張できるか?

1.4

応用

4: Hex

というゲーム

次のルールのゲームを行う． 外領域が四角形で内部が三角形に分割されている平面グラフ G を考える．また，外領 域の四角形の頂点を，時計回りの順で a, b, c, d とおく．二人のプレイヤー A と B が交互 にマークされていない頂点を選び，A は赤を，B は青をそれぞれマークする．また，初 期配置として，a, c は赤で b, d は青で，それぞれマークされているとする．このとき，A は a と c を結ぶ赤い道を，B は b と d を結ぶ青い道を作れば勝ちとなる．また，どちら もそのような道を作れなかった場合は，引き分けとする． a b c d 図 5: Hex の進行例で，A が勝った局面． 赤い頂点を四角で，青い頂点を三角で表 している． a b c d 図 6: グラフ H の構成． eA の頂点を四 角で， eB の頂点を三角で表している．何 もない G の頂点は eC である． 定理 6 このゲームにおいて，引き分けは起こらない． 証明． 引き分けが起こったと仮定する．すなわち，全ての頂点がマークされているが， 赤い a, c-道も青い b, d-道もない，と仮定する．このとき，次のように頂点集合 eA, eB, eC を

定義する． e A = {x ∈ V (G) : x は a から赤い道で到達可能 }, e B = {x ∈ V (G) : x は b から青い道で到達可能 }, e C = V (G)− eA− eB. 定義より，a_{∈ e}A かつ b∈ eB であり，また，引き分けが起こったと仮定したので，c, d∈ eC である．3 頂点が eA, eB, eC で異なる集合に属す三角形面を 3 色三角形とよぶ．次の主張が 証明の鍵である． 主張 6.1 G に 3 色三角形が存在する． 主張 6.1 が正しいとして証明を完了させる．G の 3 色三角形を xyz とおき，x ∈ eA, y∈ eB, z ∈ eC とする． eA, eB の定義より，G は赤い a, x-道と青い b, y-道をそれぞれ持つ． しかし，z の色が赤の場合は a から x を経由し z に至る赤い道が，青の場合は b から y を経由し z に至る青い道が，それぞれ存在するが，いずれにせよこれは z ∈ eC に矛盾 する． したがって，主張 6.1 を示せばよい．そのために次のグラフ H を考える． V (H) = { 内部の三角形面 } ∪ { 外領域 }, E(H) = {uv : u と v は eA と eB を結ぶ辺で隣接する}. 各点の H での次数について，次の三つが直ちにわかる． (i) 各三角形面の次数は 0, 1 または 2． (ii) 特に，次数が 1 である必要十分条件はその面が 3 色三角形であること，である． (iii) 外領域の次数は 1． ここで奇点定理と (iii) より，H に外領域以外の頂点で次数が奇数のものが存在する．(i) と (ii) より，その三角形面が 3 色三角形である． □ 演習 7 6× 6-grid において，上のゲームを行うと面白くないことを説明せよ．

1.5

応用

5: Sperner

の補題

内部が三角形に分割されている三角形 ABC を次のルールで頂点を着色する．(図 7 参 照．) このルールを満たす頂点の着色を三角形 ABC の Sperner 着色とよぶ． • 頂点 A は色 1，頂点 B は色 2，頂点 C は色 3 で塗る． • 線分 AB 上の頂点は色 1 または 2，線分 BC 上の頂点は色 2 または 3，線分 CA 上の頂点は色 3 または 1 で塗る． • 内部の頂点は色 1, 2 または 3 で塗る．

B C A 1 2 2 3 2 3 1 1 2 1 3 図 7: Sperner の補題にある着色の例．斜線が 3 色で着色された三角形である．

定理 7 (Sperner の補題) Sperner 着色された三角形 ABC において，頂点が 1, 2, 3 と 3 色で着色された三角形が存在する．(ただし，内部が空のもののみを三角形と呼ぶ．) 演習 8 定理 7 を，以下のグラフ H を用いることで定理 6 と同様の方法で示せ． 定理 8 (Brouwer の不動点定理) f を 2 次元球面から自分自身への連続写像とすると， f は不動点を持つ．(すなわち，ある点 x で f (x) = x である．) 証明． 2 次元球面ではなく T = 三角形 ABC 上の連続写像としてよい．任意の x∈ T で f (x)_{̸= x と仮定し矛盾を導く．} T0, T1, . . . を内部が小三角形に分割された三角形の列で，その小三角形の面積の最大値 が 0 に収束するもの，とする．(例えば，図 8 のようなもの) ただし，T0 = T とする．各 k ≥ 0 で Tk の頂点の着色を次のように定義する．(図 9 参照．) T0 = T A B C T1 A B C T2 A B C 図 8: 小三角形の面積の最大値が 0 に収束する三角形 T0, T1, T2, . . . の例． • 頂点 A は色 1，頂点 B は色 2，頂点 C は色 3 で塗る． • 各頂点 x では，半直線 xf(x) と Tk が交わる点が，線分 AB 上の場合は色 3 で，線 分 BC 上の場合は色 1 で，線分 CA 上の場合は色 2 でそれぞれ塗る． • ただし，半直線 xf(x) と Tk が交わる点が A である場合は，色は 2 でも 3 でも良 い．同様に，B または C で交わる場合は，それぞれ，色 1 か 3，色 1 か 2 で塗る．

• 線分 AB または BC または CA 上の頂点 x で f(x) も同じ線分にある場合は，次 のように塗る; X, Y ∈ {A, B, C} に対し，x が線分 XY 上の頂点で半直線 xf(x) が 頂点 X 方向へ向かう場合は，x を Y の色で塗る． これは  Tkの Sperner 着色となる．したがって，Sperner の補題より，Tkは頂点が 3 色で 着色された三角形を含む．この 3 色で着色された三角形の頂点で色 i のもの (i∈ {1, 2, 3}) を vi k とおく． Tk A B C x f (x) 図 9: x とその像 f (x) の例．この場合，x には色 3 を与える． T はコンパクトなので，点列 (v1 k ) k≥1 は収束する部分列を含む．その部分列を ( u1 ℓ ) ℓ≥1 とし，u1 ℓ → u (as ℓ → +∞) とおく．ここで T0, T1, . . . の小三角形の面積は 0 に収束する ため，u1 ℓ に対応する v 2 k, v 3 k の頂点をそれぞれ u 2 ℓ, u 3 ℓ とおくと，||u 1 ℓu 2 ℓ||, ||u 1 ℓu 3 ℓ|| → 0 (as ℓ→ +∞) である．したがって， u2_ℓ → u, u3_ℓ → u (as ℓ → +∞) となる． 各 ℓ ≥ 1 に対し，Tℓの着色において u1ℓ の色は 1 なので，色の塗り方より半直線 u1ℓf (u1ℓ) は線分 BC と交わる．さらに f は連続で u1 ℓ → u (as ℓ → +∞) なので，半直線 uf(u) も 線分 BC と交わる．同様に，u2 ℓ と u3ℓ を考えることで，半直線 uf (u) は線分 CA, AB と 交わることがわかり，矛盾する． _□

2

Ramsey

理論

Kn で n 頂点の完全グラフを表す．K2 を単に辺，K3 を三角形ともよぶ． 辺が着色されたグラフにおいて，ある部分グラフの辺の色がすべて同じとき，その部分 グラフを単色であるという．さらに辺の色が指定されているときは，赤い部分グラフ，青 い部分グラフのように言う．2 つのグラフ G と H に対し，G と H の (2 色) Ramsey 数 r2(G, H) を次のように定義する． r2(G, H) は以下の性質を満たす最小の正整数 N である：KN の辺をどのよう に赤・青の 2 色で着色しても，赤い G か青い H が存在する．

2.1

完全グラフの

Ramsey

数

Ramsey 数については，特に G が Kn，H が Km の場合が基本的であり，まずはこれ を調べる． 定理 9 次の二つが成り立つ．(1) r2(K2, Km) = m. (2) r2(K3, K3) = 6. 証明． (1) 次の二つを示せばよい．それぞれは簡単である． (a) (存在性) Km の辺をどのように赤・青の 2 色で着色しても，赤い K2 か青い Km が存 在する．(すべての辺が青ならば青い Km が，そうでなければ赤い K2 が存在する．) (b) (最小性) Km−1 の辺の，赤・青の 2 色でのある着色で，赤い K2 も青い Km も存在 しない．(実際に，すべての辺を青で塗ればよい．) (2) (存在性) K6 の辺の赤・青 2 色での着色を考える．ある頂点 v に注目する．v の次数 は 5 であるので v は (a) 3 本以上の赤い辺に接続する，または，(b) 3 本以上の青い辺に 接続する．対称性より，(a) が起こると仮定して良い．A を赤い辺で v と隣接する頂点集 合とおく． • A 内に赤い辺がある ⇒ v とその赤い辺で赤い K3 となる． • A 内に赤い辺がない ⇒ A の 3 頂点が青い K3 となる． いずれの場合でも赤い K3 か青い K3 が見つかった． (最小性) K5 において，赤い K3 も青い K3 も存在しないような着色が存在する． □ (存在性) の別証明. K6 に K3 は全部で (₆ 3 ) = 20 個存在する．ここで， R: 赤い K3 の個数, B: 青い K3 の個数, M : 2 色の K3 の個数 とおくと，R + B + M = 20 である． 各 2 色の K3 において，各面から 2 色の頂点へ向かって → をおく．すなわち， (→ の総数) = 2M

である．一方で，各頂点 v で，v に接続する赤い辺の数を r(v), 青い辺の数を b(v) とそ れぞれおくと，r(v) + b(v) = 5 であり，相加・相乗平均の関係より， (v に向かう → の総数) = r(v)· b(v) ≤ (_{r(v) + b(v)} 2 )2 = 25 4 である．ここで，左辺はその整数性から _{≤ 6 であり，したがって，K6} の 6 頂点すべてを 考えると， (→ の総数) ≤ 36 である．以上より，M ≤ 18 であり，R + B ≥ 2 が得られる． □ 演習 9 K7 の辺を 2 色で着色すると，単色の K3 が少なくとも 4 個存在することを示せ． 演習 _{∗ N ≥ 7 に対し，KN} の辺を 2 色で着色したときに存在する単色の K3 個数の下界 を求めよ． 定理 10 (Ramsey, 1930) 任意の n, m≥ 2 で r2(Kn, Km) は存在する．特に，次が成立 する． r2(Kn, Km)≤ r2(Kn−1, Km) + r2(Kn, Km−1). 証明． N = r2(Kn−1, Km) + r2(Kn, Km−1) とおき，KN の辺を赤・青の 2 色で着色する． 頂点 v を一つ選び， A = {u ∈ V (KN) : 辺 uv は赤で着色されている}, B = {u ∈ V (KN) : 辺 uv は青で着色されている},

と定義する．_{|A| + |B| = N − 1 より，(a) |A| ≥ r2}(Kn−1, Km) か (b) |B| ≥ r2(Kn, Km−1)

の少なくともどちらか一方が成り立つ． (a) の場合は，r2(Kn−1, Km) の定義より，A 内に赤い Kn−1 か青い Km が存在する．前 者の場合は頂点 v と合わせて赤い Kn が得られ，また後者の場合はそのままで青い Km が得られる．(b) の場合も同様にして，赤い Kn か青い Km が得られる． □ 演習 10 (b) の場合を示し，証明を完結させよ． 定理 10 より，ただちに下の式が得られる． r2(Kn, Km) ≤ ( m + n− 2 m− 1 ) . 特に，r2(Km, Km)≤ 22m−3 である．一方で，次に述べるような既存の下界は上界とは大 きな差が存在する．実際に，Ramsey 数を決定することは非常に難しい問題であり，n, m が小さい場合に関しても，r2(K4, K4) = 18 であるが 43≤ r2(K5, K5)≤ 49 としか判明し ていない． 定理 10 より，r2(K3, K4)≤ 10 は得られるが，実際には r2(K3, K4) = 9 であることが 知られている．これを示すことも容易ではない． 演習 11 r2(K3, K4)≤ 9 を示せ．

定理 11 n, p, q ≥ 2 と m = p + q − 1 に対し，以下が成り立つ． r2(Kn, Km)≥ r2(Kn, Kp) + r2(Kn, Kq)− 1. 証明． N1 = r2(Kn, Kp)− 1, N2 = r2(Kn, Kq)− 1 とおく．N = N1 + N2 としたとき， KN のある赤・青での着色で，赤い Kn も青い Km も存在しないものを見つければよい． 定義より，赤い Kn も青い Kp も存在しない KN1 のある着色が存在し，また，赤い Kn も青い Kq も存在しない KN2 のある着色が存在する．ここで，KN を N1 頂点と N2 頂 点へと分け，それぞれに上の彩色を行うことにしよう．残る辺は KN1 と KN2 を結ぶ辺で あるが，それらの辺に適切な色をぬり，所望の着色を得よ． _□ 演習 12 上の KN1 と KN2 を結ぶ辺に適当な着色をして証明を完成させよ． 演習 _{∗ 上の方法で r2}(K3, K4)≥ 8 が示せる．このときの彩色の方法を具体的に示せ． 演習 13 r2(K3, K4)≥ 9 を示せ． 定理 12 (Erd˝os, 1947) 任意の m≥ 3 に対し，次が成り立つ． r2(Km, Km) ≥ 2m/2. 証明． 定理 9 (2) より，r2(K3, K3) = 6 ≥ 2 √ 2 = 23/2 _{である．したがって，m ≥ 4 と} してよい． N < 2m/2 とし，「KN の辺の赤・青の 2 色でのある着色で，赤い Km も青い Km も存 在しない」ことを示す．N 頂点に順にラベル 1, 2, . . . , N を付け KN の辺の赤・青の 2 色 での着色全体の集合を _GN とおく．_{|GN| = 2(}N2) である． また，KN の N 頂点のうち，ある m 頂点を固定する．この m 頂点が赤い Km である ような着色は，2(N2)−( m 2) 通り存在する．したがって，K N の辺の赤・青の 2 色での着色 で，赤い Km が存在するものの集合をGNred とおくと，Km の選び方が (_N m ) 通りで，その Km が赤い塗り方は 2( N 2)−( m 2) 通りであるため，|Gred N | ≤ (_N m ) · 2(N2)−( m 2) である．ここで， (_N m ) ≤ Nm 2m−1 であること (演習 14) と N < 2m/2 という仮定，および m≥ 4 より， |Gred N | |GN| ≤ ( N m ) · 2−(m 2) ≤ N m 2m−1 2 −(m 2) < 2 m2 2 −( m 2)−m+1 = 2− m 2+1 ≤ 1 2 である．同様に，KN の辺の赤・青の 2 色での着色で青い Km が存在するものの集合を Gblue N とおくと， |Gblue N | |GN| < 1 2 が成り立つ．以上より，_{GN −}(_Gred N ∪ GNblue ) ̸= ∅ が導かれ，すなわち，ある着色で赤い Km も青い Km も存在しないことがわかり，証明が完了した． □ 演習 14 (N m ) ≤ Nm 2m−1 を示せ． なお，定理 12 の証明は構成的ではなく，m を固定し N = 2m/2_{− 1 としたとき，K} N の単色の Km が存在しない赤・青での着色を見つけるためには，すべての着色を一つず つ調べるしかない．

2.2

一般のグラフ

Ramsey

数

完全グラフ以外のグラフ G, H に対しての Ramsey 数についてもいくつかの結果が知 られている．ここでは，基本的なものとして，道，木，閉路などについて述べる．ここで， Pm で m 頂点の (長さ m− 1 の) 道を表し，Cm で m 頂点の閉路を表す． 定理 13 (Parsons, 1973) n≥ 2 に対し次が成り立つ． r2(Kn, Pm) = (n− 1)(m − 1) + 1. 下界 (最小性) の証明. N = (n− 1)(m − 1) とし，KN の赤・青の 2 色での着色で赤い Kn も青い Pm も存在しないものを構成すればよい． KN の頂点を (m− 1) 頂点づつ，(n − 1) 個のブロックに分割する．ここで，各ブロッ ク内の辺をすべて青く，また異なるブロックを結ぶ辺をすべて赤く塗る．このとき，青い 辺でできるグラフの各連結成分は m− 1 頂点しか含まないため，青い Pm は存在しない.  また，任意に n 頂点を選ぶと，ブロックは n_{− 1 個しか存在しないため，n 頂点のう} ちの少なくとも 2 頂点が同じブロックに属し，その 2 頂点は青い辺で結ばれる．したがっ て，赤い Kn も存在しないことがわかる． 上界 (存在性) の証明には次の補題を使う．これは有限数学第１において現れているた め，証明は省略する． 補題 14 最小次数が m− 1 以上の任意のグラフは頂点数 m の道を含む． 演習 _{∗ 上の補題 14 を示せ．} 上界 (存在性) の証明. n に関する帰納法で示す．N = (n− 1)(m − 1) + 1 とし，KN の 辺の赤・青の 2 色での着色を考え，赤い Kn か青い Pm が存在すること示す．n = 2 のと きは自明に成り立つため，n_{≥ 3 とする．} 演習 15 n = 2 のとき，命題が成り立つことを説明せよ． ケース 1： ある頂点 x で，x は少なくとも (n_{− 2)(m − 1) + 1 本の赤い辺に接続している．} このとき，x と赤い辺で隣接している頂点の集合を A とおくと，|A| ≥ (n−2)(m−1)+1

であるため，帰納法の仮定より，A 内に (a) 赤い Kn−1 か (b) 青い Pm が存在する．(a)

の場合はその Kn−1 に x を加えることで，KN に赤い Kn が見つかる．(b) の場合は直ち に青い Pm が存在することがわかる． ケース 2： 任意の頂点 x で，x は高々 (n− 2)(m − 1) 本の赤い辺に接続している． このとき，次の “青い” グラフ H を考える． V (H) = V (KN) E(H) = {uv : uv は青で着色されている }. ケース 2 の仮定より，δ(H)_{≥ N − 1 − (n − 2)(m − 1) = m − 1 である．ここで，補題 14} より，H は Pm を含むことがわかる．これが KN の青い Pm である． □ 実際は，補題 14 の代わりに下の補題を使うことで，もう少し強い定理 16 が示せる．

補題 15 任意の m 頂点の木と任意のグラフ H において，δ(H)≥ m − 1 ならば，H は T と同型な木を部分グラフとして含む． 定理 16 (Chv´atal, 1977) T を m 頂点の木とする．このとき，n ≥ 2 に対し次が成り 立つ． r2(Kn, T ) = (n− 1)(m − 1) + 1. 演習 _{∗ 補題 15 を m に関する帰納法で示せ．} 演習 16 Cm を m 頂点の閉路とする．このとき，m≥ 4 に対し，次の補題 17 を用いて， 以下を示せ． r2(K3, Cm) = 2m− 1. 補題 17 n≥ 3 で n 頂点のグラフ H において，δ(H) > n/2 ならば，任意の 3 ≤ k ≤ n に対し，H は長さ k の閉路を含む．

2.3

多色

Ramsey

数

k ≥ 2 と n1, . . . , nk ≥ 2 に対し，rk(Kn1, . . . , Knk) を次をみたす最小の正整数 N と して定義する．KN の辺を色 1, 2, . . . , k で着色すると，色 i の Kni が存在する．特に rk(K3, . . . , K3) を簡単のため rk(3) と書くことにする． 定理 18 任意の k ≥ 2 に対し，rk(3) は存在する． 証明． k = 2 において，r2(3) = r2(K3, K3) = 6 より，rk(3) を k に対して帰納的に上 界を求めればよい．ここでは rk(3) ≤ r2(K3, Km) を示す．ただし，m = rk−1(3) である. N = r2(K3, Km) とおく．KN の辺を色 1, . . . , k の k 色で着色し，単色の K3 が存在することを示す．ここで， 色 A = 色 1, 色 B = 色 2, . . . , k, と定義し，KN の辺が色 A, B の 2 色で着色されていると考える．このとき，N = r2(K3, Km) であることから，KN は (a) 色 A の K3 か (b) 色 B の Km を含む．(a) の場合は色 1 の K3 が存在する．また，(b) の場合，その Km の辺は色 2, . . . , k の k− 1 色で着色されて いることと m = rk−1(3) から，帰納法の仮定より，Km 内に単色の K3 が存在し，やはり 証明が完了する． _□ 演習 17 k ≥ 4 で偶数のとき，rk(3)≤ r2(Km, Km) を示せ．ただし，m = rk/2(3) である． 演習 18 r3(K3, K3, K3)≤ 17 を示せ．

2.4

多色

Ramsey

数の応用：

Schur

の定理

{1, 2, . . . , 13} を以下のように 3 つの集合に分割する． A1 ={1, 4, 10, 13}, A2 ={2, 3, 11, 12}, A3 ={5, 6, 7, 8, 9}. このとき，任意の i (1≤ i ≤ 3) と任意の x, y ∈ Ai で，x + y ̸∈ Ai である．(x = y の場合 も含む．すなわち，x ∈ Ai ならば 2x̸∈ Ai である．) しかしながら，この性質は十分に 大きな整数を用意すると成り立たないことがわかる．これを述べた次の定理が Schur に よって示されている． 定理 19 (Schur, 1916) 任意の k ≥ 1 に対し，ある N が存在して，{1, 2, . . . , N} の任 意の k 個の集合への分割 A1, . . . , Ak に対し，ある i (1 ≤ i ≤ k) とある x, y ∈ Ai で， x + y ∈ Ai となる．(ただし x = y でも可．) 証明． N = rk(3) = rk(K3, K3, . . . , K3) とおく．定理 18 より，そのような N は存在す る．_{{1, 2, . . . , N} の k 個の集合への分割 A1}, . . . , Ak を考え，ある i (1 ≤ i ≤ k) とある x, y ∈ Ai で x + y ∈ Ai を示せばよい． V (KN) = {1, 2, . . . , N} である N 頂点の完全グラフ KN において，各辺 ij を|i−j| ∈ Aℓ となる色 ℓ で着色する．これは，KN の辺の k 色での着色なので，N = rk(3) より，単 色の K3 が存在する．その色を i (1≤ i ≤ k) とおく．すなわち，ある a, b, c ∈ V (KN) で 辺 ab, bc, ac の色はすべて i である．対称性より a < b < c としてよく，このとき辺の着 色の定義から b_{− a, c − b, c − a ∈ A}i である．したがって，x = b− a かつ y = c − b と すると，x, y ∈ Ai で x + y = c− a ∈ Ai が成り立つ． □ 演習 _{∗ 定理 19 において，k = 2 のとき N = 5 で良いことを示せ．また N = 4 では不} 可であることも示せ． 演習 _{∗ 「任意の正整数 k と任意のグラフ G に対し，rk}(G, G, . . . , G) が存在する」とい う定理を使い，以下を示せ． 任意の k ≥ 1 に対し，ある N が存在して，{1, 2, . . . , N} の任意の k 個の集合への分割 A1, . . . , Ak に対し，ある i (1≤ i ≤ k) とある x, y, z ∈ Ai で，x + y + z ∈ Ai である． 定理 20 (Schur, 1916) 任意の k≥ 1 に対し，ある N が存在して，任意の p ≥ N であ る素数 p に対し，ある正整数 x, y, z が存在して，以下が成り立つ． xk+ yk ≡ zk (mod p). 証明． k≥ 1 に対し，定理 19 の N を選ぶ．任意の p ≥ N である素数 p に対し，所望 の x, y, z が存在することを示せばよい．ここで，Z∗ p を Zp − {0} 上に演算として積を考 えた群とすると，これは p が素数であるとき巡回群となることが知られている．したがっ て，_Z∗_p には生成元が存在し，それを g とおく．すなわち，任意の x∈ Z∗ p に対し，ある正 の整数 r が存在して x≡ gr _{(mod p) と書ける．さらに，0}≤ i ≤ k − 1 である i に対し， Ai :={x ∈ Z∗p : x≡ g r _{(mod p) かつ，ある j に対し r = kj + i}} と定義すると，A0, . . . , Ak−1 は {1, 2, . . . , p − 1} の分割となる．

ここで N, p の選び方より，ある i (0≤ i ≤ k − 1) とある x′_{, y}′_{, z}′ _{∈ A} i で，x′+ y′ = z′ である．さらに x′, y′, z′ ∈ Ai であることから，ある j1, j2, j3 が存在して， x′ ≡ gkj1+i_{, y}′ ≡ gkj2+i_{, z}′ ≡ gkj3+i _{(mod p)} となる．したがって，x′+ y′ = z′ であることから， gkj1+i_{+ g}kj2+i ≡ gkj3+i _{(mod p),} すなわち， gi·(gkj1 _{+ g}kj2 − gkj3) ≡ 0 _{(mod p)} である．ここで，p が素数であり，gi _{̸≡ 0 (mod p) なので} gkj1_{+ g}kj2 ≡ gkj3 _{(mod p),} であり，x = gj1_{, y = g}j2_{, z = g}j3 とおくことで所望の x, y, z が見つかった． □

2.5

Ramsey

ゲーム

完全グラフ KN において，二人のプレイヤー A と B が交互にマークされていない辺 を選び，A は赤を，B は青をそれぞれマークする．A は赤い Km を，B は青い Km を， それぞれ作れば勝ちとなる．なお，先手は A である．また，どちらもそのような Km が 作れなかった場合は引き分けとする． このゲームを Km-Ramsey ゲームとよぶ． 定理 21 任意の m に対し，ある N が存在し，KN 上の Km-Ramsey ゲームは A が必勝 である． 証明． N = r2(Km, Km) とすれば引き分けはない．A が負けないことは次の演習で示す． □ 演習 _∗ (i) m = 3, N = 5 のとき，A が必ず勝てることを示せ． (ii) m = 3, N = 4 のときはどうか? (iii) A に負けはないことを示せ．すなわち，最善を尽くすと A が勝つか引き分けである． (iv) m に対し，B が引き分けにすることができる，なるべく大きな N を見つけよ．(N = 2m− 4 のときで可能．)

定理 22 (Erd˝os & Selfridge, 1973) 任意の m と任意の N で，ℓ = (m₂)− 1 である ℓ

で 2ℓ _>(N m ) ならば KN 上の Km-Ramsey ゲームは B が引き分けにできる． 上の m, N に関する条件は，下のように書き直せる． m ≥(1 + o(1))2 log N log 2

3

ハミルトン閉路

与えられたグラフに対し，辺を順にたどり，すべての頂点をちょうど一度ずつ通り元の 頂点に戻る経路をそのグラフのハミルトン閉路，また，元の頂点に戻らなくともよいもの をハミルトン道とそれぞれ呼ぶ．

3.1

1-

タフとハミルトン閉路

ナイトはチェスの駒の一種であり，図 10 のように 1_{× 2 の長方形の対角線上に位置す} るマスに移動できる．「あるマスにいるナイトが，すべてのマスをちょうど一度ずつ通り 始めのマスに戻る」ような経路をナイトツアーと呼ぶ．また，ナイトツアーにおいて，「始 めのマスに戻らなくともよい」ことにしたものを開ナイトツアーと呼ぶ1_{．8× 8 の (通常} の) チェス盤や 5× 6 のチェス盤にはナイトツアーが存在するが，ここで考えたい問題は 存在しない場合の “理由” である． 図 10: ナイトの動き方． _{図 11: 5× 5 のチェス盤．} 命題 23 (1) 5× 5 のチェス盤 (図 11) にはナイトツアーが存在しない． (2) 4× 4 のチェス盤にもナイトツアーが存在しない． (1) の解答例：次の事実から説明できる． 「ナイトは白マスと黒マスを交互に移動する」 5× 5 のチェス盤には，白マスが 12 マス，黒マスが 13 マス存在する (またはその逆とな る) ため，すべての頂点をめぐり出発点に戻ることは不可能である． □ 4 3 2 1 a b c d 1 2 図 12: マス b2 と c3． 4 3 2 1 a _b c _d 3 2 4 1 5 5 5 5 図 13: マス b2, c2, b3, c3． (2) の解答例：図 12 にある ⃝ の 2 マス b2 と c3 に注目する2_{．ナイトが 1 a4 にいる} 場合は _{⃝ のどちらかを経由しない限り他のマスへは移動できない．これは 2 d1 でも同} 1_{これに対し，始めのマスに戻るものを閉ナイトツアーと呼ぶこともある．} 2_{チェスの表記に従い，チェス盤の行を数字で，列をアルファベットで記し，その組合せで各マスを表す．}

様である．すなわち_{⃝ の 2 マス以外は， 1 a4 のマス， 2 d1 のマス，および 3 その} 他のマス，と三つのグループへと分割され，一つのグループから他のグループへの移動に は_{⃝ のどちらかのマスを必ず使う．しかしながら ⃝ は 2 マスしか存在しないため，三} つのグループをすべて巡り始めのマスに戻ることは不可能である． _□ 問題 23 (2) の解答例 (その 2)：図 13 にある ⃝ の 4 マス b2, c2, b3, c3 に注目する．先 の解答例と同様に，a1, d1, a4, d4 の各マスにいるナイトは，⃝ のいずれかのマスを経由 しない限り他のマスへは移動できない．加えて， 5 の 4 マス b1, d2, a3, c4 のいずれか にいるナイトは，この 4 マス内は ⃝ のマスを使わずに移動可能だが，それ以外のマスへ の移動は_{⃝ のマスを経由する必要がある．これは図 13 の記号のない 4 マス c1, a2, d3,} b4 についても同様である． 結局，_{⃝ の 4 マスに対して，それ以外のマスは，a1, d1, a4, d4 の各グループ，および} b1, d2, a3, c4 のグループ，c1, a2, d3, b4 のグループ，と六つのグループへと分けられ， どのグループも他のグループへ移動するためには_{⃝ のいずれかを経由する必要がある．} したがって，どのグループから始めても _{⃝ の 4 マスだけでは 6 グループすべてにはたど} り着けず，(閉) ナイトツアーどころか開ナイトツアーさえ存在しない． □ a1 c2 c3 b2 d3 c4 d2 b3 c1 a2 b4 a4 d1 d4 b1 a3 4 3 2 1 a _b c _d 図 14: (4× 4)-ナイトグラフ． 図 15: 1-タフだが，ハミルトン閉路 をもたないグラフ このナイトツアーは，次のグラフにおけるハミルトン閉路とみなすことができる：チェ ス盤の各マス目を頂点とし，“ナイトが一手で移動できる” 関係にある頂点対を辺で結ん だグラフ．これをナイトグラフと呼ぶ．図 14 に 4× 4 のナイトグラフを示す．上の解答 例より，下の定義と命題 24 が示唆される．任意の頂点部分集合 S に対し，G から S の 頂点を取り除いてできるグラフ G− S が ω(G− S) ≤ |S| を満たす．同様に任意の頂点部分集合 S で ω(G_{− S) ≤ |S| + 1 が成り立つようなグラフ} G を弱 1-タフであるという． 命題 24 ハミルトン閉路をもつグラフは 1-タフである．また，ハミルトン道をもつグラ フは弱 1-タフである． 証明． 対偶，すなわち，「グラフ G のある頂点部分集合 S で ω(G_{− S) > |S| が成り立} つならば，G はハミルトン閉路をもたない」を示せばよい． そのような頂点部分集合 S が存在したと仮定する．このとき，G− S の一つの連結成 分の頂点を始点とする道を考えると，この道が G_{− S の他の連結成分へたどり着くため} には S の頂点を通る必要がある．したがって，ω(G− S) 個の連結成分をすべて回って始

点を含む連結成分に戻るためには同じ数の S の頂点が必要となるが，ω(G− S) > |S| で あるため，これは不可能である．これより，G はハミルトン閉路をもたないことが示さ れた． _□ なお，命題 24 の逆は一般には成り立たない．例えば，図 15 のグラフは，1-タフだが ハミルトン閉路を持たない． 演習 19 命題 24 のハミルトン道の場合に対し，逆が成り立たないことを示せ．すなわち， 弱 1-タフだがハミルトン道を持たないグラフを与えよ． チェス盤のナイトツアーについては，現在では以下の定理が知られている． 定理 25 (Schwenk) m ≤ n としたとき，m × n のチェス盤にナイトツアーが存在する ための必要十分条件は，次のいずれもが成り立たないことである． (I) m と n がともに奇数である． (II) m = 1, 2 または 4 である． (III) m = 3 であり，かつ n = 4, 6 または 8 である． 演習 _{∗ この定理 25 の十分性を示せ．} この定理 25 の必要性を考えよう．(III) の m = 3 かつ n = 8 の場合は，そのナイトグ ラフが 1-タフであるにもかかわらずナイトツアーが存在しない．しかしながら，その他 の場合はすべて，対応するナイトグラフが 1-タフではないことで示すことができる．問 題 23 (1) と同様にして (I) の場合が示せ，(II) の m = 4 かつ n = 4 の場合が問題 23 (2) に相当する．(II) の m = 1, 2 の場合は簡単なので，それ以外の場合を演習とする． 演習 20 (3× 4)-ナイトグラフ，(3 × 6)-ナイトグラフ，および，任意の n ≥ 5 に対する (4× n)-ナイトグラフのそれぞれが 1-タフではないことを示せ． 演習 21 (3_{× 8)-ナイトグラフが 1-タフであることを示せ．} 演習 _{∗ この定理 25 の開ナイトツアー版を考えよ．}

3.2

3-

正則グラフのハミルトン閉路の数

与えられたグラフに対し，

定理 26 (Smith, 1946−) G を 3-正則グラフとし，e を G の辺とする．このとき，e を

e e e 図 16: 3-正則グラフの例 (左図)．辺 e を通るハミルトン閉路はちょうど 2 個である (右図)． 証明． Thomassen による証明を紹介する．e を通るハミルトン閉路が存在しない場合， 数は 0 で OK．したがって，e を通るハミルトン閉路が存在する，としてよい． e = xy とし G′ = G− y とおく．次のグラフ H を考える． V (H) = {P : P は x を端点とする G′ のハミルトン道}, であり，P と P′ は P = v1, v2, . . . , vn−1 に対し (ただし v1 = x)，ある k (1≤ k ≤ n − 3) で，vk ∈ N(vn−1) かつ P′ = v1, v2, . . . , vk, vn−1, vn−2, . . . , vk+1 と書けるとき，かつそのときに限り H で隣接する．(図 17 参照) v1 vk vk+1 vn−2 vn−1 P v1 vk vk+1 vn−2 vn−1 P′ 図 17: H において隣接する G のハミルトン道 P と P′． 主張 26.1 P = v1, . . . , vn−1 に対し，以下が成り立つ． dH(P ) = { 2 vn−1 ̸∈ NG(y) のとき, 1 vn−1 ∈ NG(y) のとき. 証明． まず vn−1 ̸∈ NG(y) のとき, G は 3-正則なので vn−1 は vn−2 以外に 2 頂点の近傍 を持つ．それぞれの近傍が H で P に隣接するハミルトン道を作るので，dH(P ) = 2 で ある．vn−1 ∈ NG(y) のときも同様である． □ ここで，P = v1, . . . , vn−1 に対し，vn−1 ∈ NG(y) であるとき，v1, . . . , vn−1, y, x が G の ハミルトン閉路であり，辺 e を通る．また，逆に，G において e を通るハミルトン閉路 は y を取り除くことで，ある頂点 vn−1 ∈ NG(y) に対し x と vn−1 を端点とする G′ のハ ミルトン道を誘導する．したがって，主張 26.1 より，H で次数が 1 の頂点が G で e を 通るハミルトン閉路に対応する．そして奇点定理より，H で次数が奇数の頂点は偶数個 であるため，定理 26 が成り立つ． □ 演習 _{∗ G がオイラーグラフで x を G の頂点とする．このとき，}「x を端点とするハミル トン道の数」は偶数であることを示せ． 演習 _{∗ G が 3-正則グラフでハミルトン閉路を持つとき，G は少なくとも 3 つのハミル} トン閉路を持つことを示せ．

4

平面グラフの問題

定理 27 (オイラーの公式, 1750?) 平面上の任意の連結なグラフ G において，次が成り 立つ．ただし，F (G) で G の面の集合を表す． |V (G)| − |E(G)| + |F (G)| = 2.

4.1

放電法

放電法は，平面グラフ等が良い性質を持つことを示す際に用いられる重要な手法であ る．ここではその一例として，オイラーの公式を放電法で証明する． 証明． これは Thurston による証明である．平面グラフ G に対し，各辺が直線で描か れており x 軸に平行ではないとしてよい．(x 軸に平行な辺があれば，少し回転させれば よい．) まず，各頂点に +1 を，各辺に −1 をそれぞれ与える．ここでは，それぞれの値 を電荷とよぶ．このとき，次が成り立っている． (電荷の合計) =|V (G)| − |E(G)|. 各頂点，および各辺に対し，その電荷をすぐ右にある面へと渡す．(放電する という操 作である．) ここで，x 軸に平行な辺が存在しないことから，“すぐ右” は well-defined で ある．このとき，各面 f の放電後の電荷の総量を考える．f が外領域ではないときは，f は “左側” に並ぶ辺と頂点から電荷を受け取るが，そのような辺と頂点は上から順に “辺， 頂点，辺，頂点，_{· · · ，辺” と現れている．(f が 凸でないときは少し注意が必要だが，や} はりこれが成り立つ．) したがって，f が受け取る電荷の合計は −1 である．また，f が 外領域であるときは，f へ電荷を渡す頂点・辺が f の “左側” に “頂点，辺，頂点，· · · ， 頂点” と現れており，合計で +1 の電荷を受け取る．したがって， (電荷の合計) =−(|F (G)| − 1)+ 1 =−|F (G)| + 2 である．したがって，電荷の合計が放電の前後で変化しないことから，オイラーの公式が 証明できた． _□ +1 +1 +1 +1 +1 +1 −1 −1 −1 −1 −1 ₋₁ −1 −1 図 18: 定理 27 (オイラーの公式) の放電法による証明． 命題 28 G を平面の三角形分割 (外領域も三角形) とし，G の頂点数を n とする．この とき G の面の数は 2n− 4 である．

演習 22 命題 28 を放電法で示せ． ヒント：各頂点に初期電荷として +2 を与え，電荷の移動のルールを考えよ． グラフの各頂点 v に対し，v に接続する辺の本数をその頂点の次数といい dG(v) と書 き，また，各面 f に対し，f の境界の辺の本数をその面の次数といい dG(f ) と書く (こ の二つの次数はある種の双対の関係にある．) 握手補題より， _∑ v∈V (G) dG(v) = 2|E(G)| が成り立ち，またその証明と同様に，各辺がちょうど二つの面の境界に属すことより， ∑ f∈F (G) dG(f ) = 2|E(G)| が成り立つ．したがって， ∑ v∈V (G) ( dG(v)− 6 ) + ∑ f∈F (G) ( 2dG(f )− 6 ) = −12 (1) が成り立つ． 演習 23 等式 (1) をオイラーの公式を使って示せ． ここで，どのようなグラフ G でも 2 角形はありえないので，全ての面 f で dG(f )≥ 3 が成り立つ．したがって 2dG(f )− 6 ≥ 0 と等式 (1) より， ∑ v∈V (G) ( dG(v)− 6 ) ≤ −12 であり，この左辺が 0 未満のため，ある頂点 v で dG(v)− 6 < 0 である．すなわち，次 の補題が証明できた． 補題 29 任意の平面グラフには次数が 5 以下の頂点が存在する． この補題から次の彩色の結果が得られる． 定理 30 任意の平面グラフは 6 色以下で彩色できる． 等式 (1) からの帰結である補題 29 を用いることで，平面グラフの 6 色以下での彩色が 簡単な帰納法で得られた．現在では「4 色以下での彩色が可能である」という命題 (4 色 定理) が示されているが，その証明にも上のアイデアが登場する． 等式 (1) を使うもう少し複雑な例として，次の定理を示す． 次の命題は 4 色定理の証明のために考えられたものである． 定理 31 G を平面の三角形分割とする．G の最小次数が 5 ならば，G にはある辺 xy で 「x の次数が 5 で y の次数が 6 以下である」ものが存在する．

証明． そのような辺が存在しないと仮定し，矛盾を導く．まず，各頂点 v と各面 f に 次のような (初期) 電荷 ch(v) と ch(f ) を与える． ch(v) = dG(v)− 6, ch(f ) = 2dG(f )− 6 = 0. これに対し，等式 (1) より次が成り立つ． ∑ v∈V (G) ch(x) =−12. ここで，次数が  7 以上の各頂点 v は，近傍にある次数 5 の頂点に 1/5 づつ電荷を渡 し，放電後の各頂点 v の電荷の値を ch∗_{(v) と表す．} ここで各頂点 v に注目する．G の最小次数は 5 と仮定したため，ch(v)≥ −1 である． v の次数が 5 の場合，定理の仮定より v の近傍の頂点はすべて次数が 7 以上である ため， ch∗(v) ≥ (dG(v)− 6 ) +1 5 · 5 = 0 である．v の次数が 5 の場合は電荷を渡すことがないため，ch∗(v)≥ ch(v) = dG(v)−6 = 0 である．v の次数が 7 以上であると仮定する．このとき，G は三角形分割であるため，v の近傍に次数 5 の頂点は高々 ⌊dG(v) 2 ⌋ 個しか存在しない．(そうでないならば，v の近傍 に次数 5 の頂点が連続して現れ，それが所望の辺となる．) したがって， ch∗(v) ≥ (dG(v)− 6 ) −1 5 · ⌊dG(v) 2 ⌋ ≥ 9 10dG(v)− 6 ≥ 0 である．いずれの場合でも ch∗(v) ≥ 0 となり，∑_{v∈V (G)}ch(x) = −12 に矛盾している． □ 定理 32 次の条件 (∗) を満たす平面グラフは 3 色以下で彩色できる． (∗) 長さが 4 以上 11 以下の閉路が存在しない． 定理 32 は，次の補題 33 を補題 29 の代わりに用いることで，定理 30 と同様の方法で 証明できる．したがって補題 33 を示せば十分である． 補題 33 条件 (∗) を満たす平面グラフには次数が 2 以下の頂点が存在する． 証明． 条件 (∗) を満たすある平面グラフ G において「全ての頂点で次数が 3 以上であ る」と仮定し，矛盾を導く． 定理 31 の証明と同様に， ch(v) = dG(v)− 6, ch(f ) = 2dG(f )− 6, とおく．

ここで，三角形以外の各面 f は図 19 のように接続する各頂点に 3/2 ずつ電荷を渡し， 放電後の，各頂点または面 x の電荷の値を ch∗(x) と表す．この電荷の受け渡しではその 総量は変化しないため，上の式より， ∑ x∈V (G)∪F (G) ch∗(x) = ∑ x∈V (G)∪F (G) ch(x) =−12 (2) が得られる． f 図 19: 電荷の受け渡し．(矢印に沿って 3/2 ずつ渡す) 演習 24 各頂点 v および各面 f で放電後の電荷 ch∗ が 0 以上であることを示せ． 以上より，任意の頂点または面 x において ch∗(x)≥ 0 となる．したがって， ∑ x∈V (G)∪F (G) ch∗(x)≥ 0 が成り立ちますが，これは等式 (2) に矛盾し，補題 33 の証明が完了した． □ なお，定理 32 の条件 (∗) は最善ではなく，「長さが 4 以上 7 以下の閉路が存在しない」 としても正しいことが示されている．一方で，「条件 (_{∗) の “11 以下” を “5 以下” にし} ても正しい」という命題は Steinberg 予想として知られていたが，つい最近，反例が見つ かった．したがって，残る問題は「長さが 4 以上 6 以下の閉路が存在しない」場合のみ である．

4.2

四色定理と同値な命題

定理 34 (四色定理) 任意の平面グラフは 4-彩色可能である． 有名な四色定理であるが，本項ではこれと同値な二つの命題を紹介する．なお，各面が すべて三角形 (外領域も含む) の平面グラフを平面の三角形分割という．平面グラフの頂 点の彩色においては，四角形以上の面があれば対角線を加えても難しさは変わらないた め，三角形分割にのみを考えればよい．したがって，次の (I) は四色定理と同値である． また，それぞれの彩色は図 20 を参照せよ． 定理 35 平面の任意の三角形分割 G に対し，次の三つは同値である． (I) G は 4-彩色可能である．

(II) G の辺を「どの三角形にも 3 色すべてが現れている」ように 3 色で塗り分けるこ とができる．(Gr¨unbaum 彩色) (III) G の各面に +1 または−1 を割り当てて「どの頂点においても接続する面の値での 合計値が mod 3 で 0 である」とできる．(Heawood 彩色) 1 2 3 1 4 1 2 3 1 3 3 2 1 2 −1 −1 −1 +1 +1 +1 図 20: 4-彩色，Gr¨unbaum 彩色，Heawood 彩色の例． (I) ⇒ (II) の証明． G が 4-彩色 c を持つとし，色を Z2× Z2 で表す．すなわち，4 色 を (0, 0), (0, 1), (1, 0), (1, 1) とする．このとき，各辺 e = xy に対し，辺 e を c(x) + c(y) で彩色する．ただし，上の + はZ2× Z2 上での和を取っている．G の各面は三角形であ り，その 3 頂点を x, y, z とおくと，その面の 3 辺はそれぞれ c(x) + c(y), c(y) + c(z), c(x) + c(z) で彩色されている．ここで，c が G の頂点の彩色であることから c(x) ̸= c(y) であり， したがって c(x) + c(y) ̸= (0, 0) と c(x) + c(z) ̸= c(y) + c(z) が成り立つ．同様にして， 上の彩色において (0, 0) は現れず，またすべてが異なる値である．よって，これが G の Gr¨unbaum 彩色である． □ 演習 25 図 21 の平面の三角形分割 G において，(1) 4-彩色を見つけよ．(2) 定理 35 (I) ⇒ (II) の証明にならい，その 4-彩色から得られる Gr¨unbaum 彩色を見つけよ．(3) さら

に定理 35 (II) ⇒ (III) の証明にならい，その Gr¨unbaum 彩色から得られる Heawood 彩

色を見つけよ．

(II) ⇒ (III) の証明． G の Gr¨unbaum 彩色を f とおく．ただし，f の 3 色は 0, 1, 2 とする．このとき，G の各面 T に対し，辺の色 0, 1, 2 は順に時計回り，または反時計回 りに現れている．写像 φ : F (G) → {+1, −1} を，各面 T が前者のときには +1 を，後者 のときには _{−1 をそれぞれ割り当てるものとする．ただし，外領域の三角形では +1 と} −1 を逆にする．これが Heawood 彩色となることを示す． 頂点 v において，v に接続する辺を時計回りに e1, e2, . . . ek とおき，辺 ei と ei+1 に挟 まれた面を Ti とおく．(ただし，ek+1 = e1 である．) ここで，φ の定義より，

図 21: + + + + + − − − − − 図 22: が成り立つ．したがって，帰納的に考えて， f (ek+1)≡ f(ek)− φ(Tk)≡ · · · ≡ f(e1)− k ∑ i=1 φ(Ti) (mod 3) が得られるが f (ek+1) = f (e1) であるため，所望の式が成り立つ． □

(II) ⇒ (I) の証明． G の Gr¨unbaum 彩色を f とおく．ただし，f の 3 色は Z2× Z2

の元のうちの (0, 1), (1, 0), (1, 1) とする．次の主張が重要なアイデアである．(この主張の 証明は以下で演習とする．) 主張 35.1 G の任意の閉路 C に対し，次が成り立つ． ∑ e∈E(C) f (e) = (0, 0). G の頂点彩色 c を次のように構成する．G の頂点を一つ選び，その頂点 v0 の色を (0, 0) とする．v0 からはじめ，「まだ彩色されていないが彩色されている頂点と隣接する頂点」 を順に (I) _{⇒ (II) の証明の逆操作で彩色していく．すなわち，頂点 v が未彩色であるが，} 彩色済みの頂点 u と隣接しているときは， c(v) = c(u) + f (uv) と定義する．(図 23 を参照．) ただし，ここでも + は Z2× Z2 上での和を意味する． この彩色 f は Z2× Z2 を像として持つため，4 色しか使わない．そこで，c が実際に 「隣接する 2 頂点は異なる色である」こと，すなわち，任意の辺 xy に対し c(x)_{̸= c(y) を} 示す． ある辺 xy で c(x) = c(y) と仮定する．c の定義より，ある頂点列 x0, x1, . . . , xp (ただし x0 = v0 かつ xp = x) によって x まで順に頂点が彩色されている．すなわち，頂点 xi+1 の彩色に頂点 xi の彩色 c(xi) が用いられており，c(xi+1) = c(xi) + f (xixi+1) が任意の i = 0, 1, . . . , p− 1 で成り立っている．特に，任意の i で， c(x) = c(xi) + p−1 ∑ j=i f (xjxj+1) (3)

v0 (1, 0) (0, 1) _{(1, 1)} (1, 1) (1, 0) (1, 0) (0, 1) (0, 0) (1, 0) (0, 1) (1, 1) (1, 1) 図 23: Gr¨unbaum 彩色 から 4-彩色へ．(→ が 頂点の彩色の順を，□内が彩色 c を表す．) である．同様に，頂点 y の彩色のために，頂点列 y0, y1, . . . , yq (ただし y0 = v0 かつ yq = y) が用いられたとすると， c(y) = c(yi) + q−1 ∑ j=i f (yjyj+1) (4) が任意の i で成り立つ．ここで，xs= ys となる s≥ 0 を最大に取る．x0 = y0 = v0 であ るため，そのような s は存在する．ここで，上の式 (3) と (4) より， c(xs) + p−1 ∑ j=s f (xjxj+1) = c(x) = c(y) = c(ys) + q−1 ∑ j=s f (yjyj+1) すなわち， p−1 ∑ j=s f (xjxj+1) + q−1 ∑ j=s f (yjyj+1) = (0, 0) が成り立つ．(xs= ys であることと−f(yjyj+1) = f (yjyj+1) であることに注意せよ．) 一 方で，閉路 C = xs, xs+1, . . . , xp, yq, yq−1, . . . , ys+1, ys を考えると，主張 35.1 より，∑_e∈E(C)f (e) = (0, 0) である．しかし， (0, 0) = ∑ e∈E(C) f (e) = p−1 ∑ j=s f (xjxj+1) + q−1 ∑ j=s f (yjyj+1) + f (xy) であるため，これらより f (xy) = (0, 0) となり矛盾が得られる．以上より，c が G の頂点 の 4-彩色であるが示せた． □ 演習 26 主張 35.1 を，C の内部にある三角形面の集合を F (int(C)) とおき， ∑ T∈F (int(C)) ∑ e∈E(T ) f (e) を 2 通りに評価することで示せ．

(III) ⇒ (II) の証明． Heawood 彩色 φ が与えられているとする．G の一つの辺 e を 選び，e の色 f (e) は 0 とする．このとき，辺 e からはじめ，φ(T ) = +1 の面 T に接続 する辺の色は 0, 1, 2 が時計回りに，そうでない面では反時計回りに，それぞれ現れるよ うに順に辺の色を定める．これにより構成される辺の着色が Gr¨unbaum 彩色となること は (II) ⇒ (I) と同様の手法で示せるが，煩雑になるので省略する． □ 演習 _{∗ (III) ⇒ (II) の証明をきちんと述べよ．} 演習 27 図 22 の平面の三角形分割 G の Heawood 彩色において，(1) 定理 35 (III) ⇒

(II) の証明にならい，その Heawood 彩色から得られる Gr¨unbaum 彩色を見つけよ．(2)

さらに定理 35 (II) _{⇒ (I) の証明にならい，その Gr¨unbaum 彩色から得られる 4-彩色を}

見つけよ．

4.3

Sprouts

という平面上のゲーム

Sprouts という名前の次のゲームを考える．平面上の n 点に対し，二人のプレイヤー A と B が交互に次の操作を行う． (i) 現在の点のうちの 2 点 (同じ点でもよい) を選び辺で結び， (ii) その辺を細分して新しい点を加える． ただし，(i) の操作で次数が 4 以上の点を作ってはならず，また，加える辺が他の辺と交 差してもならない．(図 24 参照．) この操作を繰り返し，辺を加えられなくなったプレイ ヤーの負けとする．すなわち，最後に辺を加えたプレイヤーの勝ちである． A B A B 図 24: n = 3 の Sprouts の例 定理 36 n 点の Sprouts は高々 3n− 1 回で決着がつく．(特に，引き分けは起こらない．) 証明． 各点 x に対し，a(x) = 3−(現在の次数) とおく．すなわち，a(x) は今後，点 x から出ることが可能な辺の数を表している．また，その合計値をポテンシャル と呼ぶ． まず，初期配置において，ポテンシャルは 3n である．また，ポテンシャルは，各プレ イヤーの各ターンにおいて，(i) で 2 だけ減り，(ii) で 1 だけ増える．したがって，合計 では各ターンでポテンシャルはちょうど 1 ずつ減る．またどのような局面においてもポテ ンシャルは 1 以上であるため (最後の細分で加えられた頂点 x では a(x) = 1 であること に注意せよ)，高々 3n− 1 回しか繰り返すことができない． □ 定理 37 n 点の Sprouts は決着がつくまでに少なくとも 2n 回かかる．

証明． n 点の Sprouts に対し p 回でゲームが終了したとする．このとき，最終的には n + p 点が存在する．また，最終局面において，次数が 2 以下の頂点を未飽和という． 最終局面の各点 x に対し，(1) 未飽和の頂点の次数は 2 であり，かつ (2) 未飽和の頂 点 x の近傍 N (x) の頂点は次数が 3 である．(そうでないと，さらにゲームの操作ができ る．なお，(1) ではないときはループとして辺を加える．) さらに、二つの未飽和の点は 同じ面に隣接しないことから，未飽和な点 x と y に対し N (x) と N (y) に共通頂点は存 在しない．これより，最終局面の頂点数 n + p は，未飽和の頂点数を s とすると 3s 以上 となり， n + p≥ 3s を得る．また，定理 36 の証明にあるポテンシャルを考えると，最終局面のポテンシャル がちょうど s であることから，3n− p = s を得る．これらより s を消去すると，p ≥ 2n を得て証明が完了する． _□ 演習 _{∗ 定理 36 と 37 では Sprouts における操作の回数の上界と下界を求めているが，} それらはともに最善である．これを示せ． なお，操作の回数 p が奇数のときは A が勝ち，偶数のときは B が勝っている．実際の ゲームにおいては，2n 回 (下界) や 3n− 1 回 (上界) でゲームが終了することはまれであ り，双方が最善を尽くした際の勝敗も簡単にはわからない．(n = 3 くらいでも，すべて を解析することは難しい．試してみよ．) しかし，小さい場合の全探索の結果，次の予想 が立てられている．これはコンピュータを使うことで n≤ 44 では正しいことが示されて いる． 予想 38 n 点の Sprouts は，n≡ 0, 1, 2 (mod 6) のとき，かつそのときに限り先手が必勝 である． 演習 _{∗ 図 25 の局面で勝つ操作を示せ．} 図 25: 演習 _{∗ Sprouts の (ii) の操作において，プレイヤー A はその辺を 2 回細分することに} する．(ただしこのゲームは，特に A にとって非常につまらない．なぜか？) このとき， ゲームの終了までのかかる操作の回数が 6n− 2 回以下，8n 3 回以上であることを示せ．

Sprouts の変形版として Brusseles Sprouts という次のゲームが知られている．平面 上の n 個の小さい十字架たちを考える．このときの十字架の各辺を free end とよぶ．す

なわち，初期配置では 4n 本の free end が存在する．二人のプレイヤー A と B が交互に 次の操作を行う．

(i) free end を二つ選び辺で結び，

(ii) その辺の途中に二つの free end を持つ十字架を一つ加える．

ただし，(i) の操作で加える辺が他の辺と交差してはならない．この操作を繰り返し，最 後に辺を加えたプレイヤーの勝ちとする． A B A B 図 26: n = 3 の Brusseles Sprouts の例 定理 39 Brusseles Sprouts はちょうど 5n− 2 回でゲームが終わる．したがって，n を固 定すると，どのようにゲームを行っても勝者は同じである． 証明． n 個の十字架の Brusseles Sprouts に対し，p 回でゲームが終了したとし，終局 時のグラフを G とする．ただし，十字架の集合が G の頂点集合である．1 回の操作で ちょうど 1 つの十字架と，ちょうど 2 本の辺が加えられるため，初期状態が n 個の十字 架と 0 本の辺をもつことから， |V (G)| = n + p, かつ _{|E(G)| = 2p} である．次に G の面の数を free end の数を用いて考える．まず次の二つが成り立つ． • ゲームのどの状態においても，すべての面は少なくとも一つの free end を持つ． (操作 (i) によって新しくできた面のみを考えれば良いが，そのような面は操作 (ii) によって加えられた十字架の free end が存在する．) • 終局時には，各面は高々一つの free end しか持たない． (そうでないならば，その二つの free end を結ぶことでゲームを継続できる．) したがって，G の各面はちょうど一つの free end を持つ．また，各操作では 2 つの free end を使い 2 つの新しい free end を作るため，free end の総数は初期値 4n から変化しな い．これらより，

|F (G)| = 4n

が成り立つ．よって，オイラーの公式より

(n + p)− 2p + 4n = 2

が成り立ち，p = 5n_{− 2 を得る． □}

演習 _{∗ n 点の Brusseles Sprouts において，B は (ii) の操作で新しい十字架を加えない} ことにする．(A は通常と同じ．) このゲームの終局までの操作の回数の上界と下界を求 めよ．