§E13.21五色定理

最終更新

平面へ描くことのできる有限単純グラフについて、§D2.12 定理 3.6は彩色数が66以下であることを与えている。本記事では、この上界を55まで下げる。用いる道具は二つある。第一は、平面的グラフには次数が55以下の頂点が必ず存在することである。第二は、二つの色だけを用いる部分に沿って色を入れ替える操作であり、これを Kempe 鎖に沿った色の入れ替えという。

頂点彩色と彩色数の定義には§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と書く。

本記事の証明は、平面への描き方についての位相的な事実を四つ、証明せずに用いる。そのうち三つは本文が直接に用い、残る一つは本文が引く先行記事の結果の証明が用いる。何を認めるか、なぜ本サイトのどの単元もそれを証明していないか、およびどの文献へ委ねるかは注意 1.2に書く。彩色数の上界を44まで下げる四色定理と放電法は、次の記事へ分ける。

1 平面的グラフから取り出す二つの事実

証明の出発点は、平面的グラフには次数の小さい頂点が必ず存在するという事実である。これは Euler の公式から導かれる辺の本数の評価の帰結である。この主張は先行記事では§D2.12 定理 3.6の証明の内部にしか現れないので、本記事が独立した補題として立てる。

補題 1.1. 頂点を一つ以上もつ単純平面的グラフGGには、次数が55以下の頂点が存在する。

証明.GGの頂点の個数をnn、辺の本数をmmと書く。

n≤2n \le 2のときは、GGが単純なので各頂点の次数は11以下であり、主張が成り立つ。

n≥3n \ge 3とする。§D2.12 系 3.4によりm≤3n−6m \le 3n - 6である。握手補題（§D2.7 定理 1.2）により

∑v∈Vdeg⁡G(v)=2m≤6n−12<6n\sum_{v \in V} \deg_G(v) = 2m \le 6n - 12 < 6n

が成り立つ。すべての頂点の次数が66以上であると仮定すると∑v∈Vdeg⁡G(v)≥6n\sum_{v \in V} \deg_G(v) \ge 6nとなり、この不等式に反する。よって次数が55以下の頂点が存在する。▨

証明では、平面への描き方そのものについての事実も用いる。これらは位相幾何学に属する事実であり、本記事では証明せずに認めて用いる。

注意 1.2 (認めて用いる位相的な事実). 以下の四つを、証明せずに用いる。1 から 3 は本文が直接に用い、4 は本文が引く§D2.12 系 3.4の証明が用いる。

  1. Jordan 曲線定理と単純閉曲線の局所的な分離。平面上の単純閉曲線CCに対し、平面からCCを除いた集合はちょうど二つの連結成分に分かれ、CCはそのどちらの境界にもなっている。二つの成分を、CCの内側と外側という。一方の成分の点から他方の成分の点へ至る平面上の連続な曲線は、CCと少なくとも一点を共有する。さらに、CCの各点ppについて、ppの十分小さい近傍からCCを除いた集合は、内側に属する部分と外側に属する部分の二つへ分かれる。すなわちCCはppの近くでも内側と外側を隔てており、この局所的な分離は上の大域的な主張からは導かれない。
  2. 頂点のまわりの巡回順序。平面埋め込みが与えられたとき、頂点vvを端点とする辺は、vvのまわりを一周する順序に並ぶ。この順序をvvにおける辺の巡回順序という。vvを端点とする二本の辺vv1v v_1、vv3v v_3をとると、vvの十分近くでは、この二本がvvのまわりを二つの部分に分ける。巡回順序でvv1v v_1とvv3v v_3のあいだにある辺は一方の部分へ、そうでない辺は他方の部分へ出る。
  3. 部分グラフの平面性。平面的グラフから頂点や辺を取り除いて得られるグラフは平面的であり、もとの埋め込みから対応する点と曲線を取り除いたものが埋め込みを与える。
  4. 各辺がちょうど二つの面の境界に一度ずつ現れること。平面埋め込みが与えられたとき、各辺は面の境界に延べで二回現れる。橋でない辺は相異なる二つの面の境界に一度ずつ現れ、橋は同じ一つの面の境界に二度現れる。本記事の本文はこれを直接には引かないが、補題 1.1の証明が引く§D2.12 系 3.4の証明が、面の境界に現れる辺を延べで数えた総和が辺の本数の二倍に等しいことを得るところで、これを直接用いている。

これらは平面への描き方に固有の事実であり、グラフの組合せ的な性質だけからは導かれない。本記事の五色定理の証明は、この四つを認めたうえで完結する。

上流の連鎖でも同じ事実を用いる。補題 1.1の証明が引く§D2.12 系 3.4は、その証明で 4 を直接用いるほか、§D2.12 定理 3.2を用いる。§D2.12 定理 3.2の証明は、1 のうち Jordan 曲線定理による平面の分離を明示的に認めて用いている（各点における局所的な分離は用いない）。すなわち、1 は本記事の本文が直接に用いるだけでなく、上流でも用いられている。本記事の依存を先行記事まで展開したときに認めて用いる位相的な事実は、以上により 1 から 4 の四つである。

委ね先を明示する。1 の Jordan 曲線定理は平面の分離についての定理であり、位相空間のホモロジーを用いて証明する。この道具立ては「代数的位相幾何」が扱うが、同単元は分離定理そのものを主張として掲げていないので、本サイトのどの単元も 1 を証明していない。2 と 3 は平面への埋め込みを与えたときの局所的な性質であり、4 は平面埋め込みが定める面と辺の対応についての性質であって、これらも本サイトのどの単元も証明していない。したがって四つとも、参考文献に挙げた Diestel の平面グラフの章（Planar Graphs）へ委ねる。同章は平面への埋め込みについての位相的な準備を与えている。平面へ描くことができるかどうかを組合せ的に判定する Kuratowski の定理は本単元では扱わないが、同定理の証明も上に挙げた位相的な事実を前提とする。

2 二色だけを用いる部分に沿って色を入れ替える

彩色を組み替える操作を定める。組み替えても正しい彩色のままであることが要点である。

定義 2.1.GGの彩色ccと二つの色i≠ji \ne jに対し、色がiiまたはjjである頂点の全体が誘導するGGの部分グラフをGi,jG_{i,j}と書く。Gi,jG_{i,j}の連結成分を、彩色ccに関する(i,j)(i, j)-Kempe 鎖 (Kempe chain) という。

補題 2.2.ccをGGの彩色、i≠ji \ne jを二つの色、HHを(i,j)(i, j)-Kempe 鎖とする。HHの頂点についてだけ色iiと色jjを入れ替え、他の頂点の色を変えずに定めた割り当てをc′c'とすると、c′c'もGGの彩色である。用いる色の集合は増えない。

証明.GGの辺uvuvをとり、c′(u)≠c′(v)c'(u) \ne c'(v)を示す。

uuとvvがともにHHに属する場合を考える。c′c'はccの値に色iiと色jjの入れ替えという単射を施したものであるから、c(u)≠c(v)c(u) \ne c(v)よりc′(u)≠c′(v)c'(u) \ne c'(v)が従う。

uuとvvがともにHHに属さない場合を考える。c′(u)=c(u)c'(u) = c(u)かつc′(v)=c(v)c'(v) = c(v)であるからc′(u)≠c′(v)c'(u) \ne c'(v)である。

u∈Hu \in Hかつv∉Hv \notin Hの場合を考える。u∈Hu \in Hよりc(u)∈{i,j}c(u) \in \{i, j\}であり、色の入れ替えののちもc′(u)∈{i,j}c'(u) \in \{i, j\}である。ここでc(v)∈{i,j}c(v) \in \{i, j\}であると仮定すると、vvはGi,jG_{i,j}の頂点であり、辺uvuvはGi,jG_{i,j}の辺であるから、HHがGi,jG_{i,j}の連結成分であることにより、vvはuuと同じ連結成分、すなわちHHに属する。これはv∉Hv \notin Hに反する。よってc(v)∉{i,j}c(v) \notin \{i, j\}であり、c′(v)=c(v)∉{i,j}c'(v) = c(v) \notin \{i, j\}である。c′(u)∈{i,j}c'(u) \in \{i, j\}であるからc′(u)≠c′(v)c'(u) \ne c'(v)である。

u∉Hu \notin Hかつv∈Hv \in Hの場合には、uuとvvの役割を入れ替えて同じ議論を行えばよい。

用いる色については、c′c'の値の全体はccの値の全体に含まれるので増えない。▨

3 五色定理

3.1 証明方針

頂点の個数についての累積帰納法で進む。補題 1.1で得た次数55以下の頂点vvを取り除き、残りを55色で塗る。vvの隣接頂点に現れる色が44種類以下であれば、残った色をvvへ与えれば済む。問題は、vvの次数がちょうど55であり、隣接頂点に55色すべてが現れる場合である。この場合には、隣接頂点の二つを同じ色にすることによって空きを作る。そのために、vvのまわりの巡回順序で向かい合う二つの隣接頂点を選び、その二色だけを用いる Kempe 鎖（定義 2.1）を調べる。二つが同じ Kempe 鎖に属さなければ、一方の Kempe 鎖で色を入れ替えることによって空きが生じる。二つが同じ Kempe 鎖に属する場合には、その Kempe 鎖とvvが平面上の単純閉曲線をつくり、その内側と外側に残りの二つの隣接頂点が分かれることを用いて、別の二色について同じ操作を行う。

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

証明. 頂点の個数nnについての累積帰納法（§D2.1 命題 1.2）で示す。

n≤5n \le 5のときは、すべての頂点に相異なる色を与えれば55色以下で正しい彩色になる。

n≥6n \ge 6とし、頂点の個数がnnより少ないどの単純平面的グラフも55-彩色可能であると仮定する。GGを頂点の個数がnnの単純平面的グラフとし、平面埋め込みを一つ固定する。補題 1.1により、deg⁡G(v)≤5\deg_G(v) \le 5である頂点vvをとる。注意 1.2 (3)によりG−vG - vは平面的であり、頂点の個数はn−1n - 1である。帰納法の仮定によりG−vG - vの55-彩色ccが存在する。色は1,2,3,4,51, 2, 3, 4, 5とする。

場合 1.vvの隣接頂点に現れる色が44種類以下であるとする。現れない色が少なくとも一つあるので、その色をvvへ与えればGGの55-彩色が得られる。deg⁡G(v)≤4\deg_G(v) \le 4のときは必ずこの場合になる。

場合 2.deg⁡G(v)=5\deg_G(v) = 5であり、隣接頂点に55色すべてが現れるとする。注意 1.2 (2)により、vvにおける辺の巡回順序に沿って隣接頂点をv1,v2,v3,v4,v5v_1, v_2, v_3, v_4, v_5と並べる。仮定より五つの隣接頂点の色はすべて相異なるので、色の番号を付け替えることにより、c(vt)=tc(v_t) = t（t=1,…,5t = 1, \dots, 5）としてよい。

G−vG - vの彩色ccに関する(1,3)(1, 3)-Kempe 鎖のうち、v1v_1を含むものをHHとする。

場合 2-a.v3∉Hv_3 \notin Hとする。補題 2.2により、HHの上で色11と色33を入れ替えて得られる割り当てc′c'もG−vG - vの55-彩色である。v1∈Hv_1 \in Hであるからc′(v1)=3c'(v_1) = 3であり、v3∉Hv_3 \notin Hであるからc′(v3)=3c'(v_3) = 3のままである。v2,v4,v5v_2, v_4, v_5の色は{1,3}\{1, 3\}に属さないので、HHに属するかどうかによらず変わらない。したがってc′c'のもとでvvの隣接頂点に現れる色は3,2,3,4,53, 2, 3, 4, 5、すなわち{2,3,4,5}\{2, 3, 4, 5\}であり、色11が現れない。vvへ色11を与えればGGの55-彩色が得られる。

場合 2-b.v3∈Hv_3 \in Hとする。HHは連結であるから、G1,3G_{1,3}の中にv1v_1からv3v_3への道PPが存在する。PPの頂点の色はすべて11または33である。ここでc(v2)=2c(v_2) = 2かつc(v4)=4c(v_4) = 4であるから、v2∉Pv_2 \notin Pかつv4∉Pv_4 \notin P である。この二つを先に確かめておく。

固定した平面埋め込みにおいて、PPを描く曲線に、辺vv1v v_1と辺vv3v v_3を描く曲線を継ぎ足すと、平面上の閉曲線CCが得られる。PPは道なので頂点が相異なり、vvはG−vG - vの頂点ではないのでPPの上に無い。また埋め込みでは辺どうしが端点以外で交わらないので、CCは単純閉曲線である。CCの上にある頂点はvvとPPの頂点だけであるから、直前に確かめたことによりv2v_2もv4v_4もCCの上に無い。

注意 1.2 (2)により、vvの十分近くでは辺vv1v v_1と辺vv3v v_3がvvのまわりを二つの部分に分け、巡回順序でv1v_1とv3v_3のあいだにあるv2v_2への辺は一方の部分へ、v4v_4とv5v_5への辺は他方の部分へ出る。vvの十分小さい近傍の中でCCに属する点は、辺vv1v v_1と辺vv3v v_3の点だけであるから、この二つの部分は、その近傍からCCを除いた集合にほかならない。vvはCCの上の点であるので、注意 1.2 (1)の局所的な分離により、その集合は内側に属する部分と外側に属する部分の二つへ分かれる。したがって、vvの近くにおいてv2v_2へ向かう辺の点とv4v_4へ向かう辺の点は、CCの内側と外側に分かれる。

辺vv2v v_2は、CCを構成する辺vv1v v_1、辺vv3v v_3、およびPPの各辺のいずれとも異なる。埋め込みでは相異なる辺が共通の端点以外で交わらず、v2v_2がCCの上に無いので、辺vv2v v_2がCCと共有する点はvvだけである。辺vv4v v_4についても、CCを構成するどの辺とも異なり、v4v_4がCCの上に無いので、CCと共有する点はvvだけである。よって、辺vv2v v_2から端点vvを除いた部分は連結でCCと交わらず、平面からCCを除いた集合の一つの連結成分に含まれる。辺vv4v v_4についても同じことが成り立つ。前段で二つの辺がvvの近くで内側と外側に分かれることを見たので、v2v_2はCCの一方の側にあり、v4v_4は他方の側にある。

いま、ccに関する(2,4)(2, 4)-Kempe 鎖のうちv2v_2を含むものをH′H'とし、v4∈H′v_4 \in H'であると仮定する。するとG2,4G_{2,4}の中にv2v_2からv4v_4への道QQが存在する。QQを描く曲線は、CCの内側の点と外側の点を結ぶので、注意 1.2 (1)によりCCと少なくとも一点を共有する。埋め込みでは相異なる辺が端点以外で交わらず、相異なる頂点は相異なる点に描かれているので、共有する点はQQとCCに共通する頂点でなければならない。CCの頂点はvvとPPの頂点である。QQはG−vG - vの道であるからvvを通らない。PPの頂点の色は11または33、QQの頂点の色は22または44であるから、共通の頂点は存在しない。これは矛盾である。よってv4∉H′v_4 \notin H'である。

補題 2.2により、H′H'の上で色22と色44を入れ替えて得られる割り当てc′′c''もG−vG - vの55-彩色である。c′′(v2)=4c''(v_2) = 4であり、v4∉H′v_4 \notin H'よりc′′(v4)=4c''(v_4) = 4のままである。v1,v3,v5v_1, v_3, v_5の色は{2,4}\{2, 4\}に属さないので変わらない。したがってc′′c''のもとでvvの隣接頂点に現れる色は{1,3,4,5}\{1, 3, 4, 5\}であり、色22が現れない。vvへ色22を与えればGGの55-彩色が得られる。

いずれの場合もGGの55-彩色が得られたので、累積帰納法により、すべての単純平面的グラフは55-彩色可能である。▨

証明の場合分けを、小さな平面グラフの上で追う。次の例では、辺を一本足すだけで場合 2-a から場合 2-b へ移ることを確かめる。

例 3.2 (車輪グラフによる場合 2-a と場合 2-b の追跡). 中心の頂点vvと、vvのまわりの閉路v1v2v3v4v5v1v_1 v_2 v_3 v_4 v_5 v_1からなる車輪グラフをWWと書く。WWは頂点の個数が66、辺の本数が1010の単純平面的グラフであり、deg⁡W(v)=5\deg_W(v) = 5、vvにおける辺の巡回順序はv1,v2,v3,v4,v5v_1, v_2, v_3, v_4, v_5である。W−vW - vは閉路v1v2v3v4v5v1v_1 v_2 v_3 v_4 v_5 v_1であり、c(vt)=tc(v_t) = t（t=1,…,5t = 1, \dots, 5）はW−vW - vの55-彩色である。実際、閉路の各辺の両端の色は(1,2)(1,2)、(2,3)(2,3)、(3,4)(3,4)、(4,5)(4,5)、(5,1)(5,1)であり、いずれも相異なる。vvの隣接頂点に55色すべてが現れるので、定理 3.1の証明の場合 2 に入る。

場合 2-a が起きる例。WWを考える。G1,3G_{1,3}は色が11または33の頂点、すなわちv1v_1とv3v_3が誘導する部分グラフである。W−vW - vでv1v_1とv3v_3は隣接しないのでG1,3G_{1,3}は辺をもたず、v1v_1を含む(1,3)(1,3)-Kempe 鎖はH={v1}H = \{v_1\}であってv3∉Hv_3 \notin Hである。HHの上で色11と色33を入れ替えるとc′(v1)=3c'(v_1) = 3となり、隣接頂点の色は順に3,2,3,4,53, 2, 3, 4, 5になる。このc′c'はW−vW - vの55-彩色である（各辺の両端の色は(3,2)(3,2)、(2,3)(2,3)、(3,4)(3,4)、(4,5)(4,5)、(5,3)(5,3)）。色11が現れないのでvvへ色11を与えると、vvの色11とその隣接頂点の色3,2,3,4,53, 2, 3, 4, 5はすべて異なり、WWの55-彩色が得られる。

場合 2-b が起きる例。WWの外側の面に辺v1v3v_1 v_3を描き加えたグラフをW′W'と書く。W′W'は頂点の個数が66、辺の本数が1111の単純平面的グラフであり（3⋅6−6=12≥113 \cdot 6 - 6 = 12 \ge 11）、deg⁡W′(v)=5\deg_{W'}(v) = 5と巡回順序はWWのときと変わらない。c(vt)=tc(v_t) = tはW′−vW' - vの55-彩色である（加えた辺v1v3v_1 v_3の両端の色は11と33で異なる）。いまG1,3G_{1,3}は辺v1v3v_1 v_3をもつので連結であり、v1v_1を含む(1,3)(1,3)-Kempe 鎖はH={v1,v3}H = \{v_1, v_3\}であってv3∈Hv_3 \in Hである。すなわち場合 2-b に入る。道はP=v1v3P = v_1 v_3であり、閉曲線CCは辺v1v3v_1 v_3、辺vv1v v_1、辺vv3v v_3を継いだものである。c(v2)=2c(v_2) = 2、c(v4)=4c(v_4) = 4であるからv2∉Pv_2 \notin Pかつv4∉Pv_4 \notin Pである。辺v1v3v_1 v_3を外側の面のうちv2v_2の側を回るように描くと、CCはv2v_2を囲み、v4v_4とv5v_5はCCの外側にある。G2,4G_{2,4}はv2v_2とv4v_4が誘導する部分グラフであり、W′−vW' - vでv2v_2とv4v_4は隣接しないので、v2v_2を含む(2,4)(2,4)-Kempe 鎖はH′={v2}H' = \{v_2\}であってv4∉H′v_4 \notin H'である。H′H'の上で色22と色44を入れ替えるとc′′(v2)=4c''(v_2) = 4となり、隣接頂点の色は順に1,4,3,4,51, 4, 3, 4, 5になる。このc′′c''はW′−vW' - vの55-彩色である（各辺の両端の色は(1,4)(1,4)、(4,3)(4,3)、(3,4)(3,4)、(4,5)(4,5)、(5,1)(5,1)、および(1,3)(1,3)）。色22が現れないのでvvへ色22を与えると、W′W'の55-彩色が得られる。

一本の辺を足しただけで、(1,3)(1,3)-Kempe 鎖が二つの成分から一つの成分へ変わり、場合 2-a から場合 2-b へ移った。

注意 3.3 (66色の証明との違い).§D2.12 定理 3.6の証明では、次数55以下の頂点を取り除いたあと、隣接頂点が用いる色が高々55種類であることから、66色目が必ず空いていた。色を55色に減らすと、この空きが保証されなくなる。空きが無い場合に空きを作る操作が補題 2.2であり、その操作によって二つの隣接頂点が同じ色になることの根拠として用いるのが、単純閉曲線の内側の点と外側の点を結ぶ平面上の連続な曲線は、その単純閉曲線と少なくとも一点を共有しなければならない、という注意 1.2 (1)である。場合 2-b ではこれを次の向きで用いる。v2v_2からv4v_4への(2,4)(2,4)-Kempe 鎖の道が存在したとすると、その道は閉曲線CCと点を共有しなければならないが、CCの上の頂点の色は11または33であり道の頂点の色は22または44であるから、共有しうる頂点が存在しない。この矛盾によって、二つの隣接頂点を同じ色にすることができる。

平面性の用い方が二つの証明で異なる。§D2.12 定理 3.6は平面性を辺数の上界という数え上げの形でだけ用いる。これに対し定理 3.1は、固定した平面埋め込みそのものの性質、すなわち内側と外側の分離と、頂点のまわりの辺の巡回順序を用いる。

4 演習

問題 4.1.

  1. 定理 3.1の証明の場合 2-b について、道PP、単純閉曲線CC、Kempe 鎖H′H'の三つを、vvの隣接頂点の色を自分で指定したうえで構成し直し、v4∉H′v_4 \notin H'を導く矛盾の道筋を最初から書き下せ。
  2. 同じ証明で、v2∉Pv_2 \notin Pかつv4∉Pv_4 \notin Pという一手を省くと、どの断定が根拠を失うかを述べよ。またこの一手の根拠がPPの頂点の色の指定であることを、c(v2)c(v_2)とc(v4)c(v_4)の値を用いて説明せよ。
  3. 場合 2 で選ぶ二色の組を(1,3)(1, 3)と(2,4)(2, 4)ではなく(1,2)(1, 2)と(3,4)(3, 4)に取り替えると、証明のどの段階が成立しなくなるかを、vvのまわりの巡回順序に即して述べよ。とくに、v1v_1とv2v_2から作った単純閉曲線がv3v_3とv4v_4を分離するかどうかを判定せよ。
  4. 補題 2.2の証明を、u∈Hu \in Hかつv∉Hv \notin Hの場合だけ再現せよ。HHがGi,jG_{i,j}の連結成分であることを、どこで用いたかを明示せよ。HHをGi,jG_{i,j}の連結とはかぎらない部分グラフに取り替えると主張が成り立たない例を、道P3P_3の22-彩色について一つ作れ。
  5. 補題 1.1の証明でn≤2n \le 2の場合を分けて扱う理由を、§D2.12 系 3.4が課す仮定に即して述べよ。
  6. §D2.12 定理 3.6と定理 3.1のそれぞれについて、平面性をどのような形で用いているかを一文ずつで述べ、注意 3.3の指摘と対応づけよ。
  7. 注意 1.2 (3)を認めずに証明を進めることができるかどうかを判定せよ。判定にあたって、証明のどの行が 3 を用いているかを指摘せよ。
  8. 例 3.2のW′W'について、加える辺をv1v3v_1 v_3ではなくv2v5v_2 v_5とし、同じく外側の面へ描いたグラフを考えよ。c(vt)=tc(v_t) = tから出発したとき、場合 2-a と場合 2-b のどちらに入るかを判定し、vvへ与える色を求めよ。

6 扱った範囲と次の記事

本記事では、次数55以下の頂点が存在すること、Kempe 鎖に沿った色の入れ替えが正しい彩色を保つこと、およびすべての有限単純平面的グラフが55-彩色可能であることを証明した。ただし証明は注意 1.2の四つの位相的な事実を外部文献の結果として用いており、この意味で本記事の依存はサイトの内部で閉じていない。したがって本記事の結論は、必修の記事の根拠には用いない。辺彩色、平面以外の曲面へ描いたグラフの彩色、および平面へ描くことができるかどうかの組合せ的な判定は扱っていない。次の記事では、彩色数の上界を44まで下げる四色定理について、最小反例、不可避配置、放電規則および可約性検査が矛盾を導く証明構造を扱う。

参考文献

  1. Reinhard Diestel, Graph Theory, 6th ed., Graduate Texts in Mathematics 173, Springer, Berlin, 2025.平面への埋め込みについての位相的な準備（平面の分離と頂点のまわりの辺の巡回順序）、五色定理の定式化、および Kempe 鎖による色の入れ替えを用いる証明を参考にした。

前提記事