§E13.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 四色定理

前の記事の§E13.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 \mathbb{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

である。▨

この証明の■\blacksquareが何を意味するかを、はっきりさせておく。

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

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

したがって命題 3.1と命題 3.4の完全性は、この二つを認めたうえでのものである。委ね先は、前の記事の§E13.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 鎖に沿った色の入れ替え（§E13.21 補題 2.2）は、この組み立てでも用いられる。境界の色の並びは有限個であるから、各配置についての検査は有限回の計算で終わる。ただしその計算の量は大きく、人が手で追うことのできる規模ではない。本記事は個々の配置の検査を行わず、参考文献へ委ねる。

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

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

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

注意 5.1 (五色定理と四色定理で、記事が負う責務が異なる).§E13.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. 同じ命題の結論を「次数が55である頂点と次数が66以下である頂点を結ぶ辺が存在する」へ強めることを試みよ。同じ放電規則のもとで、次数が77の頂点についての評価がどこで止まるかを、μ∗(v)\mu^{*}(v)の上界を計算して述べよ。
  3. 命題 2.5の証明を、定義 1.2の最小性をどこで用いるかを明示して再現せよ。最小性を用いずに同じ結論を導くことができるかどうかを判定せよ。
  4. 不可避性と可約性のどちらか一方だけが示された場合に、四色定理の証明が完成しない理由を、定義 2.3と定義 2.4の主張の形に即して述べよ。
  5. 命題 3.1の証明で、面の境界が長さ33の閉路であるという仮定を落とし、各面の境界の長さが33以上であるとだけ仮定すると、等式が不等式へ変わることを確かめ、その不等式の向きを求めよ。
  6. 命題 3.4が与える不可避な配置族を、定義 2.1の形式で書き下せ。族に含まれる配置の個数を答えよ。
  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))へ取り替えたとすると、放電法による議論のどこが成り立たなくなるかを述べよ。

8 扱った範囲と次の記事

本記事では、最小反例、配置、不可避性および可約性を定義し、三段階がどのように矛盾を導くかを説明した。本文で完全に証明したのは、平面三角形分割における電荷の総和が1212であることと、放電規則の一例が与える不可避性の主張の二つである。ただしこの二つの完全性は、注意 3.2に挙げた二つの位相的な事実を認めたうえでのものである。四色定理そのもの、最小反例を平面三角形分割へ還元する手順、実際に用いる配置の全一覧、および各配置の可約性の検査は証明せず、参考文献へ委ねた。したがって定理 1.1は他の記事の根拠には用いない。次の記事では、平面グラフから離れ、有限次の二重確率行列が置換行列の凸結合として表されることを扱う。

参考文献

  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 による証明全体の形式化を参考にした。

前提記事