§E16.22四色定理と放電法

最終更新

四色定理の既知の証明は、最小反例を構造の限られた平面三角形分割へ還元し、放電法によって不可避な有限配置族を得て、各配置が可約であることを有限の計算で検査する形をとる。本記事では、この三段階によりどのように矛盾が導かれるかを説明する。配置の全一覧の検査は行わないので、本記事は四色定理の完全証明ではない。

頂点彩色と彩色数の定義には§D2.12 定義 2.1を、平面グラフと平面的グラフの区別には§D2.12 定義 3.1を用いる。断りのないかぎりG=(V,E)G=(V,E)は有限単純無向グラフとし、n=∣V∣n=\lvert V\rvert、m=∣E∣m=\lvert E\rvertと書く。本記事の本文で完全に証明するのは命題 3.1と命題 3.4の二つであり、それ以外の主張は外部文献へ委ねる。

1 四色定理

前の記事の§E16.21 定理 3.1により、有限単純平面的グラフの彩色数が55以下であることが得られた。色の個数をもう一つ減らした次の主張も正しい。

定理 1.1 (四色定理). すべての単純平面的グラフは44-彩色可能である。

本記事ではこの定理を証明しない。以下では、知られている証明がどのように組み立てられているかを述べる。以降の記述は、本記事の他の主張の根拠には用いない。

証明は、44色で塗り分けることができない単純平面的グラフのうち、頂点の個数が最小のものを考えて矛盾を導く形をとる。

定義 1.2. 四色定理が偽であると仮定する。すなわち、44-彩色可能でない有限単純平面的グラフが存在すると仮定する。そのようなグラフの頂点の個数の全体は自然数の空でない部分集合であるから、自然数の整列性により最小元をもつ。頂点の個数がこの最小元に等しく44-彩色可能でない有限単純平面的グラフを一つ選び、最小反例 (minimal counterexample) という。定義により、最小反例より頂点の個数が少ない有限単純平面的グラフはすべて44-彩色可能である。

最小反例については、平面埋め込みのすべての面の境界が長さ33の閉路であるとしてよいことが知られている。本記事ではこの還元を証明せず、参考文献に挙げた Robertson、Sanders、Seymour、Thomas の論文へ委ねる。同論文では、最小反例をより強い連結性をもつ三角形分割へ還元する手順が与えられている。素朴には、境界の長さが44以上の面の内部に弦を描き加えれば辺を増やすことができる。しかし、弦の両端の二頂点が面の外ですでに隣接している場合には弦を加えると多重辺が生じるので、単純性は無条件には保たれない。標準的な還元の手順では、この場合を別に処理する。この還元の委譲は、注意 3.2で挙げられる位相的な前提とも、配置の全一覧と可約性検査という計算による検証とも別の項目である。以下では対象を次のグラフに限る。

定義 1.3. 頂点の個数が33以上の連結な単純平面グラフGGが平面三角形分割 (plane triangulation) であるとは、固定した平面埋め込みにおけるすべての面の境界が長さ33の閉路であることをいう。

2 配置、不可避性、可約性

証明の第一段階は、最小反例のどこかに、あらかじめ用意した有限個の配置のいずれかが現れることを示すことである。第二段階は、用意した各配置が最小反例には現れないことを示すことである。二つの段階を合わせると矛盾が生じる。用語を定める。

定義 2.1. 有限単純グラフHHと写像d ⁣:V(H)→Z≥0d\colon V(H) \to \Z_{\ge 0}との組K=(H,d)K = (H, d)を配置 (configuration) という。この定義は母体となるグラフを伴わない。ddは、HHの各頂点が母体のグラフでもつべき次数の指定であり、HHにおける次数ではない。

平面三角形分割GGが配置K=(H,d)K = (H, d)を含む (contain) とは、頂点部分集合S⊆V(G)S \subseteq V(G)と、SSが誘導する部分グラフG[S]G[S]からHHへの同型写像φ\varphiであって、すべてのu∈Su \in Sに対しdeg⁡G(u)=d(φ(u))\deg_G(u) = d(\varphi(u))を満たすものが存在することをいう。ここでdeg⁡G(u)\deg_G(u)はG[S]G[S]における次数ではなく、母体GGにおける次数である。GGがKKを含むとき、KKがGGに現れる (appear) ともいう。

注意 2.2 (本記事が扱わない技術的条件). 四色定理の証明で実際に用いる配置には、上の定義に加えて、母体の中でHHの像を取り囲む閉路（環という）が存在すること、および環の内部が三角形分割であることという条件が課される。この条件は可約性の検査の手続きを定めるために必要であるが、本記事では扱わず、参考文献へ委ねる。したがって本記事の定義 2.1は、文献の配置の概念を、次数の指定という骨格だけに切り詰めたものである。

定義 2.3.G\mathcal{G}を平面三角形分割の集まりとする。配置の有限族K\mathcal{K}がG\mathcal{G}について不可避 (unavoidable) であるとは、G\mathcal{G}に属する任意のグラフがK\mathcal{K}のいずれかの配置を含むことをいう。

定義 2.4. 配置KKが可約 (reducible) であるとは、KKを含み44-彩色可能でない任意の平面三角形分割GGに対し、GGより頂点の個数が少なく44-彩色可能でない有限単純平面的グラフを構成することができることをいう。

可約な配置と最小反例の関係を、定義から導いておく。

命題 2.5. 四色定理が偽であると仮定し、最小反例G0G_0が平面三角形分割であるとする。KKを可約な配置とすると、G0G_0はKKを含まない。

証明.G0G_0がKKを含むと仮定する。G0G_0はKKを含む44-彩色可能でない平面三角形分割であるから、定義 2.4により、G0G_0より頂点の個数が少なく44-彩色可能でない有限単純平面的グラフG1G_1が存在する。一方定義 1.2により、最小反例より頂点の個数が少ない有限単純平面的グラフはすべて44-彩色可能である。これはG1G_1の取り方に反する。よってG0G_0はKKを含まない。▨

3 放電法

不可避性を示すための方法が放電法である。各頂点へ量を配り、規則に従って頂点のあいだで量をやり取りする。放電法で最初に用いるのは次の等式である。

命題 3.1.GGを平面三角形分割とすると

∑v∈V(6−deg⁡G(v))=12\sum_{v \in V} \bigl( 6 - \deg_G(v) \bigr) = 12

が成り立つ。

証明. 頂点の個数をnn、辺の本数をmm、面の個数をffと書く。各面の境界は長さ33の閉路であるから、面の境界に現れる辺を延べで数えると3f3fである。一方、各辺はちょうど二つの面の境界に一度ずつ現れる。実際、ある辺が同じ面の境界に二度現れると仮定すると、その面の境界を一周する歩道は同じ辺を二度通るので、長さ33の閉路にはならない。したがって3f=2m3f = 2m、すなわちf=23mf = \frac{2}{3} mである。

Euler の公式（§D2.12 定理 3.2）によりn−m+f=2n - m + f = 2であるから、ffを代入してn−m+23m=2n - m + \frac{2}{3} m = 2、すなわちn−13m=2n - \frac{1}{3} m = 2、m=3n−6m = 3n - 6を得る。握手補題（§D2.7 定理 1.2）により∑v∈Vdeg⁡G(v)=2m=6n−12\sum_{v \in V} \deg_G(v) = 2m = 6n - 12であるから

∑v∈V(6−deg⁡G(v))=6n−∑v∈Vdeg⁡G(v)=6n−(6n−12)=12\sum_{v \in V} \bigl( 6 - \deg_G(v) \bigr) = 6n - \sum_{v \in V} \deg_G(v) = 6n - (6n - 12) = 12

である。▨

この証明がどの事実を認めたうえで完結しているかを、次の注意で明示しておく。

注意 3.2 (電荷の総和の等式が認めて用いる位相的な事実).命題 3.1の証明は、平面への埋め込みについての位相的な事実を二つ、証明せずに認めて用いている。

  1. Jordan 曲線定理。平面上の単純閉曲線が平面を内側と外側の二つの連結成分へ分けるという定理である。本記事ではこれを直接には引かないが、証明で用いる Euler の公式（§D2.12 定理 3.2）の証明で、これを明示的に認めて用いている。
  2. 各辺がちょうど二つの面の境界に一度ずつ現れること。上の証明は、面の境界に現れる辺を延べで数えて3f=2m3f = 2mを得るところで、これを直接用いている。ある辺が同じ面の境界に二度現れないことは上の証明が示したが、相異なる二つの面の境界に一度ずつ現れること自体は、平面埋め込みの位相的な性質であり、グラフの組合せ的な性質だけからは導かれない。

したがって命題 3.1と命題 3.4の完全性は、この二つを認めたうえでのものである。委ね先は、前の記事の§E16.21 注意 1.2と同じく、参考文献に挙げた Diestel の平面グラフの章（Planar Graphs）である。本サイトのどの単元もこの二つを証明していない。この委譲は、本記事が配置の全一覧と可約性検査を Appel–Haken 以降の文献へ委ねることとは別の項目である。前者は位相的な前提であり、後者は計算による検証である。

電荷の総和の等式を、小さな具体例で検算する。正多面体のうち、面がすべて三角形であるものは正四面体、正八面体、正二十面体の三つである。これらの正多面体からは、いずれも定義 1.3の意味の平面三角形分割が得られる。

例 3.3. 面がすべて三角形である三つの正多面体について、命題 3.1の両辺を数える。頂点の個数をnn、辺の本数をmm、面の個数をffと書く。

  • 正四面体。n=4n = 4、m=6m = 6、f=4f = 4であり、すべての頂点の次数は33である。n−m+f=4−6+4=2n - m + f = 4 - 6 + 4 = 2、3f=12=2m3f = 12 = 2m、m=6=3n−6m = 6 = 3n - 6がいずれも成り立つ。電荷の総和は4⋅(6−3)=124 \cdot (6 - 3) = 12である。
  • 正八面体。n=6n = 6、m=12m = 12、f=8f = 8であり、すべての頂点の次数は44である。n−m+f=6−12+8=2n - m + f = 6 - 12 + 8 = 2、3f=24=2m3f = 24 = 2m、m=12=3n−6m = 12 = 3n - 6がいずれも成り立つ。電荷の総和は6⋅(6−4)=126 \cdot (6 - 4) = 12である。
  • 正二十面体。n=12n = 12、m=30m = 30、f=20f = 20であり、すべての頂点の次数は55である。n−m+f=12−30+20=2n - m + f = 12 - 30 + 20 = 2、3f=60=2m3f = 60 = 2m、m=30=3n−6m = 30 = 3n - 6がいずれも成り立つ。電荷の総和は12⋅(6−5)=1212 \cdot (6 - 5) = 12である。

三例とも総和は1212であり、次数の分布が異なっても総和が変わらないことを読み取ることができる。正二十面体はすべての頂点の次数が55であるから命題 3.4の仮定を満たし、実際にどの辺も次数55の頂点どうしを結んでいる。

各頂点vvへ6−deg⁡G(v)6 - \deg_G(v)という量を配る。この量をvvの電荷という。電荷の総和は1212であり、とくに正である。あらかじめ定めた規則に従って頂点のあいだで電荷をやり取りしても、総和は変わらない。総和が正である以上、やり取りののちにも電荷が正である頂点が残る。規則を注意深く選ぶと、「電荷が正である頂点が残るならば、その近くには一覧の配置のいずれかが現れる」という形の主張を導くことができる。この形の主張を導くことが、一覧が不可避であることの示し方である。

規則の形を具体的に見るために、簡単な一例を完全に証明する。次の命題の証明で用いる放電規則は、四色定理の証明で用いる規則そのものではない。しかし、この証明では、電荷の配り方、放電規則、および次数ごとの評価という三つの要素がどのように組み合わさるかを見ることができる。

命題 3.4.GGを平面三角形分割とし、GGのすべての頂点の次数が55以上であるとする。このとき、次数が55である頂点uuと、次数が77以下である頂点wwであって、uwuwがGGの辺であるものが存在する。

証明. 結論を否定する。すなわち、uwuwがGGの辺でありdeg⁡G(u)=5\deg_G(u) = 5であるならばdeg⁡G(w)≥8\deg_G(w) \ge 8が成り立つ、と仮定する。言い換えると、次数が55である任意の頂点について、そのすべての隣接頂点の次数が88以上である。

各頂点vvへ電荷μ(v)=6−deg⁡G(v)\mu(v) = 6 - \deg_G(v)を与える。命題 3.1により∑v∈Vμ(v)=12\sum_{v \in V} \mu(v) = 12である。次の放電規則に従って電荷を移す。

次数が55である各頂点は、自分に接続する各辺に沿って、その辺のもう一方の端点へ電荷15\frac{1}{5}を送る。

移動後の電荷をμ∗(v)\mu^{*}(v)と書く。各回の移動は一方の頂点から他方の頂点へ同じ量を移すだけであるから、総和は変わらず∑v∈Vμ∗(v)=12\sum_{v \in V} \mu^{*}(v) = 12である。

次数ごとにμ∗(v)\mu^{*}(v)を評価する。

deg⁡G(v)=5\deg_G(v) = 5の場合.vvは55本の辺に沿って合計5⋅15=15 \cdot \frac{1}{5} = 1の電荷を送る。仮定によりvvの隣接頂点の次数はすべて88以上であるから、vvは次数55の隣接頂点をもたず、電荷を受け取らない。よってμ∗(v)=(6−5)−1=0\mu^{*}(v) = (6 - 5) - 1 = 0である。

deg⁡G(v)∈{6,7}\deg_G(v) \in \{6, 7\}の場合.vvの次数は55ではないので、vvは電荷を送らない。vvが次数55の頂点uuと隣接すると仮定すると、uuの隣接頂点であるvvの次数が88未満となり、仮定に反する。よってvvは電荷を受け取らず、μ∗(v)=6−deg⁡G(v)≤0\mu^{*}(v) = 6 - \deg_G(v) \le 0である。

deg⁡G(v)=d≥8\deg_G(v) = d \ge 8の場合.vvは電荷を送らない。vvが受け取る電荷は、vvに接続する各辺について高々15\frac{1}{5}であるから、合計で高々d5\frac{d}{5}である。したがって

μ∗(v)≤(6−d)+d5=6−4d5≤6−325=−25<0\mu^{*}(v) \le (6 - d) + \frac{d}{5} = 6 - \frac{4d}{5} \le 6 - \frac{32}{5} = -\frac{2}{5} < 0

である。

すべての頂点の次数が55以上であるから、以上の三つの場合がVVを尽くす。いずれの場合もμ∗(v)≤0\mu^{*}(v) \le 0であるから∑v∈Vμ∗(v)≤0\sum_{v \in V} \mu^{*}(v) \le 0となり、∑v∈Vμ∗(v)=12\sum_{v \in V} \mu^{*}(v) = 12に反する。よって仮定は誤りであり、次数が55である頂点であって、次数が77以下の隣接頂点をもつものが存在する。▨

命題 3.4を定義 2.3の言葉で読み直す。G\mathcal{G}を、すべての頂点の次数が55以上である平面三角形分割の集まりとする。一辺のグラフK2K_2の二頂点をuu、wwと書き、d(u)=5d(u) = 5かつd(w)=jd(w) = jという次数の指定を与えた組をDjD_jと置く。定義 2.1では母体を伴わない対として配置が定められているので、D5D_5、D6D_6、D7D_7はそれだけで配置である。この三つを集めた族{D5,D6,D7}\{D_5, D_6, D_7\}は、G\mathcal{G}について不可避である。配置の個数は33である。四色定理の証明で必要になる族は、この族よりはるかに多くの配置からなる。

4 可約性の検査

第二段階は、一覧の各配置が定義 2.4の意味で可約であることを示すことである。可約性は、配置の境界に現れる頂点の色の並びを場合分けし、より小さいグラフの四色彩色から、もとのグラフの四色彩色を組み立てることができることを確かめる形で示す。Kempe 鎖に沿った色の入れ替え（§E16.21 補題 2.2）は、この組み立てでも用いられる。境界の色の並びは有限個であるから、各配置についての検査は有限回の計算で終わる。ただしその計算の量は大きく、人が手で追うことのできる規模ではない。本記事では個々の配置の検査を行わず、参考文献へ委ねる。

5 三段階が矛盾を導く仕組み

以上の三段階を組み合わせる。四色定理が偽であると仮定して最小反例をとり、平面三角形分割へ還元する。第一段階により、この最小反例は一覧のいずれかの配置を含む。第二段階により一覧の各配置は可約であるから、命題 2.5により、最小反例は一覧のどの配置も含まない。二つの結論は両立しないので、最小反例は存在しない。したがって44-彩色可能でない有限単純平面的グラフは存在せず、定理 1.1が従う。

四色定理と五色定理の違いは、配置の一覧の規模にある。Appel と Haken が19771977年に発表した証明では、配置の一覧は千個を超える大きさをもち、各配置の可約性の確認は、境界の彩色を多数調べる有限の計算に帰着される。Robertson、Sanders、Seymour、Thomas が19971997年に与えた証明では、配置の個数が633633、電荷をやり取りする規則の個数が3232まで減ったが、それでも人が手で追うことのできる規模ではなく、確認は計算機によって行われる。20082008年には Gonthier が、証明全体を定理証明支援系 Coq の上で形式化したことを報告している。四色定理については、計算機による検査を用いない証明は知られていない。

注意 5.1.§E16.21 定理 3.1は前の記事で証明した。ただしその証明は、平面の分離と頂点のまわりの巡回順序という位相的な事実を外部文献へ委ねている。したがって五色定理は、依存がサイトの内部で閉じておらず、必修の記事の根拠には用いない。定理 1.1では主張と証明の組み立て方が述べられただけで、証明されていない。したがって四色定理は、どの記事の根拠にも用いない。四色定理を根拠として用いる主張を書くときは、本記事ではなく、上に挙げた文献のどの版のどの結果を用いるのかを明示する必要がある。

なお、18791879年に Kempe が四色定理の証明として発表した議論は、18901890年に Heawood によって、場合分けの一つが正しくないことが指摘された。その議論のうち正しい部分から得られるのが、前の記事で証明した五色定理である。すなわち、五色定理は四色定理の証明の失敗の副産物として得られたものであり、証明の難しさが色の個数を一つ減らすところで大きく変わることが示されている。

6 演習

問題 6.1.

  1. 命題 3.4の証明で、放電規則の送る量を15\frac{1}{5}から16\frac{1}{6}へ取り替えると、どの次数の場合の評価が成り立たなくなるかを求めよ。その場合のμ∗(v)\mu^{*}(v)の値を計算して示せ。
  2. GGを平面三角形分割とし、GGのすべての頂点の次数が55以上であるとする。平面三角形分割では、各頂点vvの隣接頂点をvvにおける辺の巡回順序に沿ってw1,…,wdw_1, \dots, w_dと並べると、wiwi+1w_i w_{i+1}（1≤i≤d1 \le i \le d、wd+1=w1w_{d+1} = w_1）がすべてGGの辺であることを認めてよい。このとき、次数が55である頂点と次数が66以下である頂点を結ぶ辺が存在することを、命題 3.4の証明と同じ電荷と放電規則を用いて証明せよ。
  3. 四色定理が偽であると仮定し、最小反例G0G_0が平面三角形分割であるとする。k∈{0,1,2,3,4}k \in \{0, 1, 2, 3, 4\}に対し、一頂点のグラフK1K_1の頂点xxにd(x)=kd(x) = kを指定した配置をLk=(K1,d)L_k = (K_1, d)と置く。各LkL_kが定義 2.4の意味で可約であることを示し、G0G_0のすべての頂点の次数が55以上であることを導け。k=4k = 4の場合には§E16.21 問題 4.1 (2)を用いてよい。さらに、(2)を用いて、G0G_0が次数55の頂点と次数66以下の頂点を結ぶ辺をもつことを示せ。
  4. すべての頂点の次数が44以上である平面三角形分割の集まりをG4\mathcal{G}_4とし、L4L_4、L5L_5を(3)と同じく次数の指定が44、55である一頂点の配置とする（L5L_5はK1K_1の頂点に55を指定したものである）。G∈G4G \in \mathcal{G}_4において、次数が44の頂点の個数をn4n_4、次数が55の頂点の個数をn5n_5とすると2n4+n5≥122 n_4 + n_5 \ge 12であることを示し、族{L4,L5}\{L_4, L_5\}がG4\mathcal{G}_4について不可避であることを導け。さらに、例 3.3の正八面体と正二十面体を用いて、{L4}\{L_4\}と{L5}\{L_5\}はどちらもG4\mathcal{G}_4について不可避でないことを示せ。
  5. 命題 3.1の証明で、面の境界が長さ33の閉路であるという仮定を落とし、各面の境界の長さが33以上であるとだけ仮定すると、等式が不等式へ変わることを確かめ、その不等式の向きを求めよ。
  6. すべての頂点の次数が55以上である平面三角形分割の集まりをG\mathcal{G}とし、D5D_5、D6D_6、D7D_7を本文の配置とする。{D5,D6,D7}\{D_5, D_6, D_7\}の部分集合のうちG\mathcal{G}について不可避であるものをすべて求めよ。ただし、正十二面体の平面グラフ（2020頂点、3030辺、各頂点の次数は33、各面の境界は長さ55の閉路であり、各頂点はちょうど三つの面の境界に現れる）の各面の内部に新しい頂点を一つずつ置き、その面の境界の55頂点と結んで得られる3232頂点9090辺のグラフが平面三角形分割であることは認めてよい。
  7. 定義 2.1の「含む」の条件のdeg⁡G(u)=d(φ(u))\deg_G(u) = d(\varphi(u))をdeg⁡G[S](u)=d(φ(u))\deg_{G[S]}(u) = d(\varphi(u))に取り替えた定義を考える。この定義のもとでGGが配置K=(H,d)K = (H, d)を含むならば、すべてのx∈V(H)x \in V(H)についてd(x)=deg⁡H(x)d(x) = \deg_H(x)であることを示せ。さらに、この定義のもとでは、どの平面三角形分割もD5D_5、D6D_6、D7D_7のいずれも含まないこと、およびK2K_2の二頂点にともに11を指定した配置だけからなる族が、すべての平面三角形分割の集まりについて不可避であることを示せ。
解答.

(1)では、命題 3.4の証明の仮定と記号をそのまま用い、次数が55である各頂点が自分に接続する各辺に沿って電荷16\frac{1}{6}を送る規則に取り替える。deg⁡G(v)=5\deg_G(v) = 5の場合、vvは合計5⋅16=565 \cdot \frac{1}{6} = \frac{5}{6}の電荷を送り、仮定により次数55の隣接頂点をもたないので電荷を受け取らない。したがって

μ∗(v)=(6−5)−56=16>0\mu^{*}(v) = (6 - 5) - \frac{5}{6} = \frac{1}{6} > 0

であり、この次数の場合の評価μ∗(v)≤0\mu^{*}(v) \le 0が成り立たなくなる。deg⁡G(v)∈{6,7}\deg_G(v) \in \{6, 7\}の場合の議論は送る量を用いないので、vvは電荷を送りも受け取りもせず、μ∗(v)=6−deg⁡G(v)≤0\mu^{*}(v) = 6 - \deg_G(v) \le 0のままである。deg⁡G(v)=d≥8\deg_G(v) = d \ge 8の場合、vvが受け取る電荷は合計で高々d6\frac{d}{6}であるから

μ∗(v)≤(6−d)+d6=6−5d6≤6−406=−23<0\mu^{*}(v) \le (6 - d) + \frac{d}{6} = 6 - \frac{5d}{6} \le 6 - \frac{40}{6} = -\frac{2}{3} < 0

であり、評価は成り立つ。よって成り立たなくなるのは次数55の場合だけであり、その場合の値はμ∗(v)=16\mu^{*}(v) = \frac{1}{6}である。

(2)を示す。結論を否定し、次数が55である任意の頂点について、そのすべての隣接頂点の次数が77以上であると仮定する。各頂点vvへ電荷μ(v)=6−deg⁡G(v)\mu(v) = 6 - \deg_G(v)を与え、次数が55である各頂点が自分に接続する各辺に沿って電荷15\frac{1}{5}を送る規則に従って電荷を移す。移動後の電荷をμ∗(v)\mu^{*}(v)と書くと、命題 3.1より∑v∈Vμ∗(v)=12\sum_{v \in V} \mu^{*}(v) = 12である。

deg⁡G(v)=5\deg_G(v) = 5の場合. 仮定によりvvは次数55の隣接頂点をもたないので電荷を受け取らず、μ∗(v)=1−5⋅15=0\mu^{*}(v) = 1 - 5 \cdot \frac{1}{5} = 0である。

deg⁡G(v)=6\deg_G(v) = 6の場合.vvが次数55の頂点uuと隣接すると、uuの隣接頂点であるvvの次数が77未満となって仮定に反する。ゆえにvvは電荷を受け取らず、μ∗(v)=0\mu^{*}(v) = 0である。

deg⁡G(v)=7\deg_G(v) = 7の場合.vvの隣接頂点を巡回順序に沿ってw1,…,w7w_1, \dots, w_7と並べ、wiw_iの次数が55である添字iiの集合をIIとする。i∈Ii \in Iかつi+1∈Ii + 1 \in I（添字は77を法とする）とすると、次数55の頂点wiw_iが次数55の頂点wi+1w_{i+1}と隣接することになり、仮定に反する。ゆえにIIは巡回的に隣り合う二つの添字を含まない。i∈Ii \in Iに二元集合{i,i+1}\{i, i+1\}を対応させると、IIの相異なる元i,ji, jに対して{i,i+1}∩{j,j+1}≠∅\{i, i+1\} \cap \{j, j+1\} \ne \varnothingならばj=i+1j = i + 1またはi=j+1i = j + 1となってIIが隣り合う二つの添字を含むので、これらの二元集合は互いに素である。いずれも77元集合{1,…,7}\{1, \dots, 7\}の部分集合であるから、§D2.2 定理 2.1より2∣I∣≤72\lvert I\rvert \le 7であり、∣I∣≤3\lvert I\rvert \le 3である。vvは電荷を送らず、受け取る電荷は∣I∣5≤35\frac{\lvert I\rvert}{5} \le \frac{3}{5}であるから、μ∗(v)≤−1+35=−25<0\mu^{*}(v) \le -1 + \frac{3}{5} = -\frac{2}{5} < 0である。

deg⁡G(v)=d≥8\deg_G(v) = d \ge 8の場合.命題 3.4の証明と同じく、μ∗(v)≤6−4d5≤−25<0\mu^{*}(v) \le 6 - \frac{4d}{5} \le -\frac{2}{5} < 0である。

すべての頂点の次数は55以上であるから、以上の場合がVVを尽くし、∑v∈Vμ∗(v)≤0\sum_{v \in V} \mu^{*}(v) \le 0となって∑v∈Vμ∗(v)=12\sum_{v \in V} \mu^{*}(v) = 12に反する。よって、次数が55である頂点と次数が66以下である頂点を結ぶ辺が存在する。本文の証明で次数77の頂点について用いた評価は、各辺に沿って高々15\frac{1}{5}を受け取るというものであり、これでは上界が25\frac{2}{5}になる。隣接頂点の巡回順序についての事実を用いると、受け取る電荷を35\frac{3}{5}まで抑えることができる。

(3)を示す。k∈{0,1,2,3,4}k \in \{0, 1, 2, 3, 4\}とし、GGをLkL_kを含み44-彩色可能でない平面三角形分割とする。定義 2.1により、deg⁡G(u)=k\deg_G(u) = kを満たす頂点uuが存在する。G−uG - uは§E16.21 注意 1.2 (3)により平面的であり、GGの部分グラフであるから単純であって、頂点の個数はGGより一つ少ない。G−uG - uが44-彩色ccをもつと仮定する。k≤3k \le 3のとき、uuの隣接頂点に現れる色は33種類以下であるから、現れない色をuuへ与えるとGGの44-彩色が得られる。k=4k = 4のとき、§E16.21 問題 4.1 (2)をGG、uu、ccに適用すると、GGの44-彩色が得られる。いずれの場合もGGが44-彩色可能でないことに反する。ゆえにG−uG - uは、GGより頂点の個数が少なく44-彩色可能でない有限単純平面的グラフであり、LkL_kは可約である。

G0G_0がある頂点uuでdeg⁡G0(u)=k≤4\deg_{G_0}(u) = k \le 4を満たすとすると、S={u}S = \{u\}とuuをxxへ写す写像によりG0G_0はLkL_kを含む。これは命題 2.5に反する。ゆえにG0G_0のすべての頂点の次数は55以上である。

したがってG0G_0は、すべての頂点の次数が55以上である平面三角形分割であり、(2)により、次数が55である頂点と次数が66以下である頂点を結ぶ辺をもつ。

(4)を示す。G∈G4G \in \mathcal{G}_4とする。命題 3.1より∑v∈V(6−deg⁡G(v))=12\sum_{v \in V}(6 - \deg_G(v)) = 12である。次数が66以上の頂点の項は00以下であり、次数が44の頂点の項は22、次数が55の頂点の項は11であって、G∈G4G \in \mathcal{G}_4であるから次数が33以下の頂点はない。ゆえに

12=∑v∈V(6−deg⁡G(v))≤2n4+n512 = \sum_{v \in V}(6 - \deg_G(v)) \le 2 n_4 + n_5

である。とくにn4+n5≥6>0n_4 + n_5 \ge 6 > 0であり、次数が44または55である頂点uuが存在する。S={u}S = \{u\}とuuをK1K_1の頂点へ写す写像により、GGはL4L_4またはL5L_5を含む。G∈G4G \in \mathcal{G}_4は任意であったから、{L4,L5}\{L_4, L_5\}はG4\mathcal{G}_4について不可避である。

正八面体から得られる平面三角形分割はすべての頂点の次数が44であるからG4\mathcal{G}_4に属し、次数が55の頂点をもたないのでL5L_5を含まない。ゆえに{L5}\{L_5\}はG4\mathcal{G}_4について不可避でない。正二十面体から得られる平面三角形分割はすべての頂点の次数が55であるからG4\mathcal{G}_4に属し、次数が44の頂点をもたないのでL4L_4を含まない。ゆえに{L4}\{L_4\}はG4\mathcal{G}_4について不可避でない。二つの例では、それぞれ2n4+n5=2⋅6=122 n_4 + n_5 = 2 \cdot 6 = 12と2n4+n5=122 n_4 + n_5 = 12であり、不等式の等号が成り立つ。

(5)では、GGを頂点の個数が33以上の連結な単純平面グラフとし、固定した平面埋め込みの各面FFの境界の長さℓ(F)\ell(F)、すなわち境界を一周する閉じた歩道がたどる辺の延べ本数が33以上であると仮定する。§E16.21 注意 1.2 (4)により各辺は面の境界に延べで二回現れるので

∑Fℓ(F)=2m\sum_{F} \ell(F) = 2m

であり、各面についてℓ(F)≥3\ell(F) \ge 3であるから3f≤2m3f \le 2mである。命題 3.1の証明で等式3f=2m3f = 2mを得た箇所が、この不等式に変わる。§D2.12 定理 3.2によりf=2−n+mf = 2 - n + mであるから、3(2−n+m)≤2m3(2 - n + m) \le 2m、すなわちm≤3n−6m \le 3n - 6である。握手補題（§D2.7 定理 1.2）により∑v∈Vdeg⁡G(v)=2m≤6n−12\sum_{v \in V} \deg_G(v) = 2m \le 6n - 12であるから

∑v∈V(6−deg⁡G(v))=6n−2m≥6n−(6n−12)=12\sum_{v \in V} \bigl( 6 - \deg_G(v) \bigr) = 6n - 2m \ge 6n - (6n - 12) = 12

を得る。不等式の向きは≥\geであり、電荷の総和は1212以上である。等号は3f=2m3f = 2mのとき、すなわちすべての面についてℓ(F)=3\ell(F) = 3のときに限って成り立つ。たとえば立方体グラフQ3Q_3では、すべての面の境界の長さが44であり、すべての頂点の次数が33であるから、左辺は8⋅(6−3)=248 \cdot (6 - 3) = 24であって1212より大きい。

(6)では、不可避な部分集合はちょうど{D5,D6}\{D_5, D_6\}と{D5,D6,D7}\{D_5, D_6, D_7\}の二つであることを示す。まず、GGがDjD_jを含むことは、deg⁡G(u)=5\deg_G(u) = 5かつdeg⁡G(w)=j\deg_G(w) = jを満たす辺uwuwが存在することと同値である。実際、DjD_jを含めば、S={u,w}S = \{u, w\}とG[S]G[S]からK2K_2への同型写像φ\varphiがあり、G[S]G[S]は辺uwuwをもち、次数の条件が成り立つ。逆にそのような辺uwuwがあれば、S={u,w}S = \{u, w\}と、uuを次数55が指定された頂点へ、wwを他方の頂点へ写す写像が条件を満たす。

{D5,D6}\{D_5, D_6\}を含む部分集合は不可避である。G∈GG \in \mathcal{G}とすると、(2)により、deg⁡G(u)=5\deg_G(u) = 5かつdeg⁡G(w)≤6\deg_G(w) \le 6を満たす辺uwuwがある。G∈GG \in \mathcal{G}よりdeg⁡G(w)≥5\deg_G(w) \ge 5であるから、deg⁡G(w)∈{5,6}\deg_G(w) \in \{5, 6\}であり、前段によりGGはD5D_5またはD6D_6を含む。

D5D_5を含まない部分集合は不可避でない。例 3.3の正二十面体から得られる平面三角形分割は、すべての頂点の次数が55であるからG\mathcal{G}に属する。この三角形分割のどの辺も両端点の次数が55であるから、前段によりD6D_6もD7D_7も含まない。

D6D_6を含まない部分集合は不可避でない。問題文の3232頂点のグラフをPPとし、正十二面体の頂点を旧頂点、各面に置いた頂点を新頂点と呼ぶ。新頂点は、その面の境界の55個の旧頂点とだけ隣接するので、次数は55である。旧頂点は、正十二面体の33本の辺と、自分が境界に現れる三つの面の新頂点への33本の辺をもつので、次数は66である。ゆえにPPはG\mathcal{G}に属する。PPの辺は、旧頂点どうしを結ぶ辺と、新頂点と旧頂点を結ぶ辺だけであり、新頂点どうしは隣接しない。したがって次数55の頂点を端点にもつ辺のもう一方の端点の次数は66であり、PPはD5D_5もD7D_7も含まない。∑v(6−deg⁡P(v))=12⋅1+20⋅0=12\sum_{v}(6 - \deg_P(v)) = 12 \cdot 1 + 20 \cdot 0 = 12であり、命題 3.1と一致する。

以上より、部分集合が不可避であることと、D5D_5とD6D_6の両方を含むことは同値であり、該当する部分集合は{D5,D6}\{D_5, D_6\}と{D5,D6,D7}\{D_5, D_6, D_7\}である。とくに、本文の族{D5,D6,D7}\{D_5, D_6, D_7\}からD7D_7を除いても不可避性は保たれるが、それ以上は除くことができない。

(7)を示す。GGが取り替えた定義のもとでK=(H,d)K = (H, d)を含むとし、SSと同型写像φ ⁣:G[S]→H\varphi \colon G[S] \to Hをとる。u∈Su \in Sに対し、φ\varphiはuuのG[S]G[S]における隣接頂点の全体をφ(u)\varphi(u)のHHにおける隣接頂点の全体へ写す全単射を与えるので、§D2.2 命題 1.5よりdeg⁡G[S](u)=deg⁡H(φ(u))\deg_{G[S]}(u) = \deg_H(\varphi(u))である。取り替えた条件とあわせるとd(φ(u))=deg⁡H(φ(u))d(\varphi(u)) = \deg_H(\varphi(u))である。φ\varphiは全射であるから、すべてのx∈V(H)x \in V(H)についてd(x)=deg⁡H(x)d(x) = \deg_H(x)である。

DjD_j（j=5,6,7j = 5, 6, 7）はK2K_2の一方の頂点aaにd(a)=5d(a) = 5を指定するが、deg⁡K2(a)=1≠5\deg_{K_2}(a) = 1 \ne 5である。ゆえに前段により、取り替えた定義のもとでは、どのグラフもDjD_jを含まない。

K2K_2の二頂点にともに11を指定した配置をK′K'とする。平面三角形分割GGは頂点を33個以上もつ連結グラフであるから辺uwuwをもつ。S={u,w}S = \{u, w\}と置くと、G[S]G[S]は一本の辺からなり、K2K_2と同型であって、deg⁡G[S](u)=deg⁡G[S](w)=1\deg_{G[S]}(u) = \deg_{G[S]}(w) = 1である。ゆえにGGは取り替えた定義のもとでK′K'を含み、族{K′}\{K'\}はすべての平面三角形分割の集まりについて不可避である。この不可避性は母体GGにおける次数について何も述べないので、命題 3.4のように母体の次数についての結論を与える放電法の議論は、取り替えた定義のもとでは配置の出現として書くことができない。▨

参考文献

  1. Reinhard Diestel, Graph Theory, 6th ed., Graduate Texts in Mathematics 173, Springer, Berlin, 2025.平面への埋め込みについての位相的な準備（Jordan 曲線定理による平面の分離と、各辺がちょうど二つの面の境界に一度ずつ現れること）を参考にした。
  2. Kenneth Appel and Wolfgang Haken, Every planar map is four colorable. Part I - Discharging, Illinois Journal of Mathematics 21 (1977), no. 3, 429–490.放電法によって不可避配置族を得る手順と、配置の一覧の規模を参考にした。
  3. Neil Robertson, Daniel P. Sanders, Paul Seymour, and Robin Thomas, The four-colour theorem, Journal of Combinatorial Theory, Series B 70 (1997), 2–44.633 個の配置と 32 個の放電規則による証明の構成、および可約性検査の手続きを参考にした。
  4. Georges Gonthier, Formal Proof - The Four-Color Theorem, Notices of the American Mathematical Society 55 (2008), no. 11, 1382–1393.定理証明支援系 Coq による証明全体の形式化を参考にした。

前提記事