# 平面グラフ：Euler の公式・双対・五色定理 > 辺を折れ線で描いた平面グラフについて、位相の入力を Jordan の曲線定理 1 つにまとめ、Euler の公式 n − m + f = 2、辺数の上界と K_5・K_{3,3} の非平面性、面の境界と双対グラフ、正多面体の分類、Kempe 鎖による五色定理を証明する。 > https://rikai.mugen-giken.com/mathematics/graph-theory/planar-graphs ## 0. この記事の要点 点と線をつないだ図を、紙の上で線どうしを交差させずに描けるでしょうか。この記事では、描けるかどうかを点・線・区切られた領域の数え上げだけで判定する方法（Euler の公式）を示します。あわせて、地図の隣り合う国を違う色で塗り分けるのに 5 色あれば足りること（五色定理）も示します。読み終えると、3 軒の家と 3 つの供給所をどの組も管でつなぐ問題がなぜ解けないかを、式で説明できます。 - 辺を折れ線で、交差なしに平面に描いたグラフを**平面グラフ**、そう描けるグラフを**平面的グラフ**といいます。位相の入力は Jordan の曲線定理だけで、それを「閉路に乗る辺の両側は異なる面、[橋](/mathematics/graph-theory/paths-cycles-trees#def-bridge)（取り除くとつながりが切れる辺）の両側は同じ面」（）と「森の面は 1 つ」（）の形に直して使います。 - 連結な平面グラフの頂点数 $n$、辺数 $m$、面数 $f$ は $n-m+f=2$ を満たします（**Euler の公式**、）。面の数は描き方によりません。 - $n\ge3$ の平面的グラフでは $m\le3n-6$、[内周](/mathematics/graph-theory/paths-cycles-trees#def-connected)（グラフに含まれる閉路の最短の長さ）が $g$ なら $m\le g(n-2)/(g-2)$ です。ここから $K_5$ と $K_{3,3}$ が平面的でないこと、平面的グラフには次数 5 以下の頂点があることが従います。 - 2-連結（どの 1 頂点を除いてもつながっている）な平面グラフの面の境界は閉路です（）。面を頂点とする**双対グラフ**では、閉路と極小カット、[全域木](/mathematics/combinatorics/graphs-and-determinants#def-graph)（全頂点を含む閉路のない連結な部分グラフ）とその補集合が入れ替わります（）。 - どの頂点の次数も $d\ge3$、どの面の次数も $k\ge3$ である連結な平面グラフでは、組 $(d,k)$ は 5 通りしかなく、頂点・辺・面の数も $(d,k)$ で決まります（**正多面体**の 5 種類に対応、）。 - 平面的グラフは 5 色で彩色できます（**五色定理**、）。4 色で足りること（四色定理）は、計算機による膨大な場合分けを含むので主張だけを述べ、19 世紀の Kempe の議論がどこで破れるかを例で確かめます。 ## 1. 動機 3 軒の家と、水道・ガス・電気の 3 つの供給所があります。どの家もどの供給所とも管でつなぎたいのですが、管どうしを交差させたくありません。紙の上でいくら試しても、9 本目の管がどうしても引けません。これは工夫が足りないのではなく、**原理的に不可能**です。この章では、その理由が $2+2=4$ と同じくらい確かな数え上げ（Euler の公式）に帰着することを示します。 Euler の公式 $n-m+f=2$ は、凸多面体の頂点・辺・面の数の関係として 18 世紀に見つかりました。[凸多面体](/mathematics/hs-geometry/solids-spheres-polyhedra#def-convex-polyhedron)の 1 つの面を取り除いて残りを平面に押し広げれば、多面体は平面に描いたグラフになるので、同じ式が平面グラフについて成り立ちます。この式が強力なのは、「交差なしに描ける」という幾何的な条件を、「辺が多すぎない」という数の条件に変えてくれるからです。 ただし、数え上げを始める前に、「面」とは何か、辺を 1 本足すと面はどう変わるかを確定させる必要があります。ここで平面の位相が入ります。この章では、辺を**折れ線**に限ることで局所的な議論を初等的にし、大域的な入力を Jordan の曲線定理（）の 1 つにまとめます。位相の議論は §2 に閉じ込め、§3 以降は数え上げだけで進めます。 グラフの語彙は [第 1 章](/mathematics/graph-theory/paths-cycles-trees)、2-連結性と耳分解は [第 3 章](/mathematics/graph-theory/connectivity-and-flows) に従います。位相の用語（連結、連結成分）は [連結性](/mathematics/topology/connectedness) のとおりです。 ## 2. 平面グラフと面 ### 2.1. 定義 平面 $\mathbb{R}^2$ の点 $p_0,p_1,\dots,p_k$（$k\ge1$）を順に線分で結んだ集合 $[p_0,p_1]\cup\cdots\cup[p_{k-1},p_k]$ で、隣り合う線分が共有点を 1 つだけもち、隣り合わない線分が交わらないものを、$p_0$ と $p_k$ を結ぶ**折れ線の弧**という。$p_0,p_k$ を**端点**、それ以外の点を**内点**という。$p_k=p_0$（$k\ge3$）とし、最初と最後の線分も $p_0$ だけを共有することを許して同じ条件を課したものを**折れ線の閉曲線**という。 折れ線の弧は閉区間 $[0,1]$ と、折れ線の閉曲線は円周 $S^1$ と同相です（各線分を区間や円弧の一部に長さに比例して対応させればよい）。弧から端点を除いた集合は開区間の連続像なので連結です（、）。 **平面グラフ**とは、有限集合 $V\subseteq\mathbb{R}^2$（頂点）と、折れ線の弧の有限集合 $E$（辺）の組で、次を満たすものをいう。 - 各辺の両端点は $V$ の相異なる 2 点で、異なる辺の端点の組は異なる。 - 各辺の内点は、$V$ の点でも、他の辺の点でもない。 平面グラフは、頂点集合 $V$、辺の端点の組を辺とする（抽象的な）グラフを定める。両者を同じ記号 $G$ で表し、頂点と辺の和集合である点集合も $G$ と書く。辺 $e$ から端点を除いた集合を $\mathring e$ と書く。あるグラフ $H$ と同型な平面グラフを $H$ の**描画**といい、描画をもつグラフを**平面的グラフ**という。 開集合 $\mathbb{R}^2\setminus G$ の連結成分を $G$ の**面**といい、面の個数を $f(G)$ と書く。 $G$ は有界な[閉集合](/mathematics/complex-analysis/complex-numbers#def-open-set)なので、十分大きな円板の外側（連結）は $G$ と交わらず、1 つの面に含まれます。これを**外面**、ほかの面を**内面**といいます。平面グラフから頂点や辺を除いたものも平面グラフなので、平面的グラフの[部分グラフ](/mathematics/graph-theory/paths-cycles-trees#def-subgraph)は平面的です。 位相の準備を 1 つしておきます。次の補題は、平面から $G$ を除いた部分がいくつの「面」に分かれるかを、辺を足したり除いたりしても追えるようにするための道具です。後の節で、辺を 1 本除くと面がどうつながるかを調べるときに使います。 $U\subseteq\mathbb{R}^2$ を開集合とする。 1. $U$ の連結成分は開集合である。 2. $A\subseteq U$ が空でない連結な開集合で、$A$ の閉包と $U$ の共通部分が $A$ に等しいならば、$A$ は $U$ の連結成分である。 3. $U$ が、空でない連結な開集合の族 $\{A_i\}$ の非交和であるならば、$U$ の連結成分はちょうど $A_i$ たちである。 **1.** $K$ を連結成分、$x\in K$ とします。$U$ は開なので $x$ 中心の開円板 $D\subseteq U$ が取れます。円板は、どの 2 点も線分で結べるので連結です（）。$K$ は $x$ を含む連結集合のうち最大（ の 2）なので $D\subseteq K$ です。 **2.** $A$ を含む連結成分を $K$ とします（同命題の 2 から存在します）。$A$ は $K$ の開集合です。$K\setminus A=K\setminus\overline A$（仮定から $\overline A\cap K\subseteq\overline A\cap U=A$）も $K$ の開集合です。$K\setminus A\ne\varnothing$ なら $(A,K\setminus A)$ は $K$ の分離（）となり、$K$ の連結性に反します。よって $A=K$ です。 **3.** $A_i$ の外の点 $x\in U$ は別の $A_j$ に属し、$A_j$ は $A_i$ と交わらない開集合なので、$x$ は $A_i$ の閉包に入りません。よって $\overline{A_i}\cap U=A_i$ で、2 から各 $A_i$ は連結成分です。$U$ の点はどれかの $A_i$ に属するので、これですべてです。 ### 2.2. 局所的な形と、辺の両側の面 辺が折れ線であることの利点は、各点の近くでの $G$ の形が完全に分かることです。頂点のまわりでは、小さな円板が出ていく辺によって扇形に切り分けられます（下の図）。
p p S S'
$G$ を平面グラフ、$p\in G$ とする。十分小さい半径 $r>0$ の開円板 $D=D(p,r)$ について、$D\cap G$ は $p$ から出る $k$ 本の半径（線分）の和集合である。ここで、$p$ が辺の内点なら $k=2$、$p$ が頂点なら $k$ はその次数である（$k=0$ のときは $D\cap G=\{p\}$）。$D\setminus G$ は、$k\ge1$ なら隣り合う半径に挟まれた $k$ 個の開いた扇形（$k=1$ のときは切れ込みの入った円板 1 つ）、$k=0$ なら穴あき円板で、これらの各部分は連結であり、したがって $G$ の 1 つの面に含まれる。 $G$ は有限個の線分の和集合です。$p$ が線分の端点でない内部の点であるときは、その線分を $p$ で 2 つに分けておきます。すると $p$ を含む線分はすべて $p$ を端点とし、その本数は、$p$ が頂点なら次数、辺の内点なら 2 です（平面グラフの条件から、辺の内点は他の辺にも頂点にも属しません）。$p$ を含まない線分は $p$ を含まない閉集合なので $p$ から正の距離にあります。$r$ を、これらの距離と、$p$ を含む線分の長さのどれよりも小さく取れば、$D\cap G$ は $p$ から出る $k$ 本の半径になります。相異なる半径は $p$ 以外で交わらないので、向きが相異なります。 $D$ から $k\ge1$ 本の半径を除いた残りは、偏角が隣り合う半径の間にある点の集合（扇形）$k$ 個に分かれます。扇形の 2 点は、同じ扇形の中で「原点からの距離を保って偏角を動かし、次に偏角を保って距離を動かす」道で結べるので、扇形は連結です（）。穴あき円板も同じ理由で連結です。$G$ と交わらない連結集合は 1 つの面（連結成分）に含まれます（ の 2）。 辺の内点 $p$ では、$D\setminus G$ は 2 つの扇形です。これを $p$ での辺の**両側**と呼びます。 辺の両側の面について、次の補題は 3 つのことを言います。辺に沿って両側の面は変わらないこと、その辺を除くと両側の面が 1 つにつながること、葉の辺では両側が同じ面になることです。これらは、後で辺を 1 本ずつ除きながら面を数える帰納法の土台になります。 $G$ を平面グラフ、$e$ をその辺とする。 1. $\mathring e$ の点 $p$ での両側の扇形を含む面の（順序を考えない）組は、$p$ によらない。これを $f_1(e),f_2(e)$ と書く（一致することもある）。 2. 面 $f$ の閉包が $\mathring e$ の点を含むのは、$f\in\{f_1(e),f_2(e)\}$ のとき、そのときに限る。このとき閉包は $e$ 全体を含む。 3. **（辺を除くと両側の面がつながる）** $G-e$ の面は、$f_1(e)\cup\mathring e\cup f_2(e)$ と、$G$ のそれ以外の面である。とくに $f_1(e)\ne f_2(e)$ なら $f(G-e)=f(G)-1$、$f_1(e)=f_2(e)$ なら $f(G-e)=f(G)$ である。 4. **（孤立点）** $v$ が次数 0 の頂点なら $f(G-v)=f(G)$ である。 5. **（葉）** $e$ の端点の一方の次数が 1 なら $f_1(e)=f_2(e)$ である。 6. 頂点 $v$ が面 $f$ の閉包に属し、$d(v)\ge1$ ならば、$v$ は $f\in\{f_1(e'),f_2(e')\}$ である辺 $e'$ の端点である。 **1.** $p\in\mathring e$ とし、 の円板を $D_p$、2 つの扇形を $S,S'$ とします。$D_p\cap\mathring e$ の点 $q\ne p$ は 2 本の半径の一方の上にあります。$q$ 中心の十分小さい円板は $D_p$ に含まれ、その半径によって 2 つの半円板に分かれます。半径は $S$ と $S'$ の両方の縁なので、半円板の一方は $S$ に、他方は $S'$ に含まれます。よって $q$ での両側の面の組は $p$ でのものと同じです。つまり、面の組を値とする $\mathring e$ 上の関数は局所的に一定です。ある値を取る点の集合も、取らない点の集合も $\mathring e$ の開集合で、$\mathring e$ は連結なので、この関数は一定です。 **2.** $p\in\mathring e$ のとき、$D_p\setminus G=S\cup S'\subseteq f_1(e)\cup f_2(e)$ なので、$D_p$ と交わる面は $f_1(e),f_2(e)$ だけです。一方、$p$ は $S$ と $S'$ の両方の閉包に属します。よって $p$ を閉包に含む面はちょうど $f_1(e)$ と $f_2(e)$ です。$\mathring e$ の全点がその閉包に属し、閉包は閉集合なので、$e$ の端点も含みます。 **3.** $U'=\mathbb{R}^2\setminus(G-e)=(\mathbb{R}^2\setminus G)\cup\mathring e$ です。$W=f_1(e)\cup\mathring e\cup f_2(e)$ と置きます。$p\in\mathring e$ について $D_p\subseteq W$ なので、$W$ は開集合です。$\mathring e$ の 1 点 $p_0$ を固定すると、$f_1(e)\cup D_{p_0}\cup f_2(e)$ は、連結な $D_{p_0}$ が $f_1(e)$ とも $f_2(e)$ とも交わるので連結です（ を 2 回使います）。各 $D_p$（$p\in\mathring e$）は連結で $f_1(e)$ と交わるので、これらをすべて合わせた $W$ も連結です。$G$ のほかの面は連結な開集合で、$W$ と合わせて $U'$ を非交和に分けます。 の 3 から、これらが $G-e$ の面のすべてです。 **4.** $v$ のまわりの穴あき円板 $D\setminus\{v\}$ は 1 つの面 $f$ に含まれます。$f\cup\{v\}=f\cup D$ は連結な開集合で、$G$ のほかの面と合わせて $\mathbb{R}^2\setminus(G-v)$ を非交和に分けます。3 と同じく、これらが $G-v$ の面のすべてで、個数は変わりません。 **5.** 次数 1 の端点を $v$ とします。$D(v,r)\setminus G$ は切れ込みの入った円板 1 つで、ある面 $f$ に含まれます。$D(v,r)\cap\mathring e$ の点 $q$ の両側の半円板は、十分小さく取れば $D(v,r)\setminus G$ に含まれるので、どちらも $f$ に含まれます。 **6.** $v$ のまわりの円板 $D$ は $f$ と交わり、$D\setminus G$ は扇形に分かれるので、ある扇形が $f$ に含まれます。その扇形の縁の半径は $v$ を端点とするある辺 $e'$ の一部で、その上の点 $q$ の片側の半円板はこの扇形に含まれます。よって $f\in\{f_1(e'),f_2(e')\}$ です。 平面グラフ $G$ の面 $f$ に対し、$f\in\{f_1(e),f_2(e)\}$ である辺 $e$ の集合を $E_f$ と書く。$E_f$ の辺とその端点（および $f$ の閉包に属する孤立点）からなる $G$ の部分グラフを $f$ の**境界**という。 の 2 と 6 から、その点集合は $f$ の閉包から $f$ を除いた集合に一致する。$f$ の**次数**を $$ \deg(f)=\#\{(e,i): e\in E(G),\ i\in\{1,2\},\ f_i(e)=f\} $$ と定める。両側が同じ面 $f$ である辺は 2 回数える。 各辺は両側に 1 つずつ面をもつので、数え方から $$ \sum_{f}\deg(f)=2m $$ が成り立ちます。握手補題（）の面についての対応物です。 ### 2.3. Jordan の曲線定理と、閉路・橋・森 $C$ を折れ線の閉曲線とする。$\mathbb{R}^2\setminus C$ はちょうど 2 つの連結成分（有界な**内部**と、非有界な**外部**）をもち、どちらも開集合で、$C$ の各点はどちらの成分の閉包にも属する。 $C$ は円周 $S^1$ から平面への連続な単射の像です。Jordan の曲線定理（、$n=2$）から、$\mathbb{R}^2\setminus C$ はちょうど 2 つの連結成分をもち、一方は有界、他方は非有界で、どちらも開集合、$C$ はどちらの成分の境界にもなっています。境界の点は閉包に属します。 折れ線の場合には、一般の Jordan の曲線定理を使わない初等的な証明もあります。どの線分とも平行でない方向を 1 つ固定し、点 $x\notin C$ からその方向に出る半直線が $C$ と交わる回数（頂点を通るときは、$C$ が半直線を横切るときだけ数える）の偶奇を $\pi(x)$ とします。$\pi$ は $\mathbb{R}^2\setminus C$ の上で局所的に一定で、線分をまたぐと変わるので、成分は 2 つ以上あります。高々 2 つであることは、$C$ に沿って細い帯の中を進めば、どの点も $C$ の決まった 1 点の近くの 2 つの側のどちらかへ $C$ と交わらずに行けることから分かります。この章では の証明として一般の定理を使いますが、必要な位相はこの程度のものです。 閉路を含まない平面グラフ（森の描画）の面は、ちょうど 1 つである。 頂点数と辺数の和についての帰納法（）です。頂点のない平面グラフの面は $\mathbb{R}^2$ 全体の 1 つです。辺がなく頂点 $v$ があれば、 の 4 から $f(G)=f(G-v)$ で、帰納法の仮定から $f(G-v)=1$ です。辺があれば、辺をもつ成分は 2 頂点以上の木なので、次数 1 の頂点があります（ の 2）。それを端点とする辺を $e$ とすると、 の 5 から $f_1(e)=f_2(e)$、同 3 から $f(G)=f(G-e)$ です。$G-e$ も森なので、帰納法の仮定から $f(G-e)=1$ です。 次の補題は、Euler の公式の証明の核心です。閉路の上の辺は、閉路の内側と外側を隔てているので、両側の面が異なります。橋は閉路に乗らないので、どちら側から見ても同じ面です。証明の前半は Jordan の曲線定理から直接従い、後半は閉路に乗る辺の本数についての帰納法です。 $G$ を平面グラフ、$e$ をその辺とする。 1. $e$ が $G$ の閉路 $C$ に乗っていれば、$f_1(e)\ne f_2(e)$ である。すなわち $e$ はちょうど 2 つの面の境界に含まれる。さらに、この 2 つの面は $\mathbb{R}^2\setminus C$ の異なる連結成分に含まれる。 2. $e$ が橋ならば、$f_1(e)=f_2(e)$ である。すなわち $e$ はただ 1 つの面の境界に含まれる。 $G$ の面は連結で、$G$ の部分グラフである閉路の点集合とは交わらないので、その閉路の内部か外部のどちらか一方に含まれます。これを繰り返し使います。 **1.** $p\in\mathring e$ を取り、 の円板 $D_p$ と両側の扇形 $S,S'$ を取ります。$D_p\cap G\subseteq e\subseteq C$ なので、$D_p\setminus C=S\cup S'$ です。 から、$p$ は $C$ の内部の閉包にも外部の閉包にも属するので、内部も外部も $D_p\setminus C$ と交わります。$S$ と $S'$ はそれぞれ連結で $C$ と交わらないので、一方が内部に、他方が外部に含まれます。$S$ を含む面 $f_1(e)$ と $S'$ を含む面 $f_2(e)$ は、$C$ の内部と外部に分かれて含まれるので、相異なります。 **2.** $G$ の辺のうち閉路に乗るものの本数についての帰納法です。0 本なら $G$ は森で、 から面は 1 つなので、$f_1(e)=f_2(e)$ です。 閉路 $C$ に乗る辺 $e'$ があるとします。$e$ は橋なので閉路に乗らず（）、$e\ne e'$ です。$G'=G-e'$ でも $e$ は閉路に乗らず、$G'$ の閉路に乗る辺は $G$ より少ないので、帰納法の仮定から、$G'$ では $e$ の両側は同じ面です。$a=f_1(e)$、$b=f_2(e)$（$G$ での面）とし、$a\ne b$ と仮定します。$p\in\mathring e$ での円板 $D_p$ と扇形は $G$ でも $G'$ でも同じです。 の 3 から、$G'$ の面は、$G$ の面のうち $f_1(e')$ と $f_2(e')$ をつなげたものと、それ以外の面です。$a$ と $b$ が $G'$ で同じ面に含まれるのは、$\{a,b\}=\{f_1(e'),f_2(e')\}$ のときだけです。すると 1 から、$a$ と $b$ は $\mathbb{R}^2\setminus C$ の異なる成分に含まれます。ところが、円板 $D_p$ は連結で、$D_p\cap G\subseteq\mathring e$ は $C$ と交わらないので、$\mathbb{R}^2\setminus C$ の 1 つの成分に含まれ、$a$ も $b$ も $D_p$ と交わるので、同じ成分に含まれます。矛盾です。よって $a=b$ です。 平面グラフ $G$ が閉路を含むならば、どの面 $f$ についても、$E_f$ は $G$ のある閉路の辺をすべて含む。とくに $G$ の内周を $g$ とすると $\deg(f)\ge g$ である。 頂点集合が $V(G)$、辺集合が $E_f$ の平面グラフを $H$ とします。$f$ は連結な開集合で、$H\subseteq G$ と交わりません。$f$ の閉包から $f$ を除いた集合は、$G$ の点からなり（ほかの面は $f$ と交わらない開集合なので、その点は $f$ の閉包に入りません）、 の 2 から、辺の内点であれば $E_f$ の辺の点です。よってこの集合は $H$ に含まれ、$\overline f\cap(\mathbb{R}^2\setminus H)=f$ です。 の 2 から、$f$ は $H$ の面です。 $E_f$ が閉路を含まないとすると、$H$ は森で、 から面は 1 つ、すなわち $f=\mathbb{R}^2\setminus H$ です。$G$ の辺 $e\notin E_f$ があれば、$\mathring e$ は $H$ と交わらないので $f$ に含まれますが、$f$ は $G$ と交わらないので矛盾です。よって $E(G)=E_f$ で、$G=H$ は森となり、$G$ が閉路を含むことに反します。 したがって $E_f$ はある閉路の辺をすべて含み、その長さは $g$ 以上なので、$\deg(f)\ge|E_f|\ge g$ です。 ここまでで位相の議論は終わりです。以後は、、、、 を使った数え上げだけで進みます。 ## 3. Euler の公式とその帰結 連結な平面グラフの頂点数 $n$、辺数 $m$、面数 $f$ は $$ n-m+f=2 $$ を満たす。 辺数 $m$ についての帰納法（）です。 $G$ が閉路を含まなければ、$G$ は木で、$m=n-1$（ の 5）、$f=1$（）なので、$n-(n-1)+1=2$ です。 $G$ が閉路を含むとし、閉路に乗る辺 $e$ を取ります。$e$ は橋でないので $G-e$ は連結です（）。 の 1 から $f_1(e)\ne f_2(e)$ で、 の 3 から $f(G-e)=f-1$ です。$G-e$ は辺が $m-1$ 本の連結な平面グラフなので、帰納法の仮定から $n-(m-1)+(f-1)=2$、すなわち $n-m+f=2$ です。 証明の中身は、「閉路に乗る辺を 1 本除くと、辺が 1 本減り、その両側の 2 つの面が 1 つにつながる」の繰り返しです。全域木まで減らせば面は 1 つになります。 連結成分が $c$ 個の平面グラフでは $n-m+f=1+c$ が成り立つ。とくに、同じグラフの描画の面の数は、描き方によらない。 閉路に乗る辺の本数についての帰納法です。閉路がなければ森で、$m=n-c$（ の 1）、$f=1$（）なので $n-(n-c)+1=1+c$ です。閉路に乗る辺 $e$ があれば、$G-e$ は成分数が同じ $c$ で（）、面が 1 つ少ない（ の 1 と の 3）ので、 の証明と同じ計算で従います。$f=1+c-n+m$ は抽象的なグラフだけで決まります。 $n\ge3$ 頂点の平面的グラフ $G$ の辺数 $m$ は $$ m\le3n-6 $$ を満たす。さらに $G$ が閉路を含み、内周が $g$ であれば $$ m\le\frac{g}{g-2}\,(n-2) $$ である。 $G$ の描画を 1 つ取ります。$G$ が閉路を含まなければ森で、$m\le n-1\le3n-6$ です（$n\ge3$ のとき $3n-6-(n-1)=2n-5>0$）。 $G$ が閉路を含むとし、内周を $g\ge3$ とします。 からどの面の次数も $g$ 以上なので、面の次数の和について $$ 2m=\sum_f\deg(f)\ge g\,f $$ です。 と $c\ge1$ から $f=1+c-n+m\ge2-n+m$ です。代入して $2m\ge g(2-n+m)$、整理して $(g-2)m\le g(n-2)$ を得ます。$g/(g-2)=1+2/(g-2)$ は $g$ について減少するので、$g\ge3$ から $m\le3(n-2)$ も従います。 完全グラフ $K_5$ と完全二部グラフ $K_{3,3}$ は平面的でない。 $K_5$ は $n=5$、$m=10$ で、$3n-6=9<10$ です。 の第 1 の不等式に反します。 $K_{3,3}$ は $n=6$、$m=9$ です。二部グラフなので奇閉路を含まず（）、長さ 4 の閉路はあるので、内周は $g=4$ です。 の第 2 の不等式は $m\le\frac42\cdot4=8$ を要求しますが、$m=9$ です。 冒頭の「3 軒の家と 3 つの供給所」は $K_{3,3}$ の描画を求める問題でした。8 本までは引けて 9 本目が引けない、という経験は、上界 $8$ と正確に合っています。[第 5 章](/mathematics/graph-theory/kuratowski-theorem) の Kuratowski の定理は、平面的でないグラフには必ず $K_5$ か $K_{3,3}$ が（辺を細分した形で）隠れていることを示します。 頂点を 1 つ以上もつ平面的グラフには、次数が 5 以下の頂点がある。 $n\le2$ なら次数は 1 以下です。$n\ge3$ なら、握手補題（）と から $\sum_vd(v)=2m\le6n-12<6n$ なので、次数が 6 未満の頂点があります。 Petersen グラフ（）は $n=10$、$m=15$、内周 $5$ です。 の第 2 の不等式は $m\le\frac53\cdot8=13.3\cdots$ を要求するので、平面的ではありません。$3n-6=24$ なので、第 1 の不等式だけでは判定できません。内周の情報が効いています。 頂点 $1,\dots,5$ の $K_5$ から辺 $45$ を除いたグラフ（$m=9=3n-6$）は、次のように描けます。$2=(0,0)$、$1=(0,3)$、$3=(0,-3)$、$4=(-2,0)$、$5=(2,0)$ と置き、辺 $12,23,41,42,43,51,52,53$ を線分で、辺 $13$ を $(0,3)\to(5,0)\to(0,-3)$ という折れ線で描きます。線分どうしは端点以外で交わらず、折れ線は $x\ge0$ の側で $5=(2,0)$ の右を回るので、ほかの辺と交わりません。面は、三角形 $124,\ 234,\ 125,\ 235$、折れ線と $15,53$ で囲まれた面、外面の 6 つで、$5-9+6=2$ です。 すべての頂点の次数が 3 で、すべての面の次数が 5 か 6 である連結な平面グラフを考えます（サッカーボールやフラーレンの骨格）。五角形が $p$ 枚、六角形が $h$ 枚とすると、握手補題と面の次数の和から $3n=2m=5p+6h$、Euler の公式から $n-m+(p+h)=2$ です。$n=2m/3$ を代入すると $p+h-m/3=2$、すなわち $6p+6h-2m=12$ で、$2m=5p+6h$ を代入して $p=12$ を得ます。六角形の枚数によらず、五角形はちょうど 12 枚です。 ## 4. 面の境界と双対 ### 4.1. 2-連結な平面グラフの面の境界 木の描画では、ただ 1 つの面の境界はグラフ全体で、閉路ではありません。2-連結であれば、面の境界は必ず閉路になります。第 3 章の耳分解を使い、耳を 1 本足すと面がどう分かれるかを調べます。 この補題の狙いは、2-連結な平面グラフに耳を 1 本足すと、1 つの面がちょうど 2 つに分かれ、新しい面の境界がまた閉路になることを確かめることです。足した耳 $P$ の両端で、もとの面の境界の閉路を 2 本の道 $Q_1,Q_2$ に分けると、新しい 2 つの面の境界は $Q_1\cup P$ と $Q_2\cup P$ になります。 $H$ を 2-連結な平面グラフで、どの面の境界も閉路であるものとする。平面グラフ $G$ が $H$ に耳 $P$（両端 $a\ne b$ が $H$ の頂点で、内部の頂点と辺が $H$ に属さない道）を足したものであるとする。このとき次が成り立つ。 1. $P$ の $a,b$ 以外の点は $H$ の 1 つの面 $f$ に含まれ、$a,b$ は $f$ の境界の閉路 $C_f$ の上にある。 2. $C_f$ を $a$ と $b$ で 2 本の道 $Q_1,Q_2$ に分ける。$G$ の面は、$H$ の $f$ 以外の面（境界は $H$ でのものと同じ）と、$f$ に含まれる 2 つの面で、後者の境界は閉路 $Q_1\cup P$ と $Q_2\cup P$ である。 **1.** $P$ は折れ線の弧で、端点を除いた集合 $\mathring P$ は連結で $H$ と交わらないので、$H$ の 1 つの面 $f$ に含まれます。$a,b$ は $\mathring P$ の閉包、したがって $f$ の閉包に属する $H$ の点なので、$f$ の境界 $C_f$ の上にあります。 **2.** *$f$ 以外の面.* $H$ の面 $h\ne f$ は、連結な開集合で、$G$ と交わらず（$\mathring P\subseteq f$）、閉包から $h$ を除いた集合は $H\subseteq G$ に含まれます。 の 2 から $h$ は $G$ の面です。$H$ の辺の内点での両側の扇形は $H$ でも $G$ でも同じなので、$H$ で片側が $h$ である辺は $G$ でもそうで、$P$ の辺の両側は $f$ の中にあります。よって $h$ の境界は変わりません。 *面の数.* $P$ の長さを $\ell$ とすると、$G$ は $H$ より頂点が $\ell-1$ 個、辺が $\ell$ 本多い連結な平面グラフです。 から $f(G)=f(H)+1$ です。$G$ の面は $H$ と交わらない連結集合なので $H$ のある面に含まれ、それが $h\ne f$ なら $h$ 自身です。したがって、$f$ に含まれる $G$ の面はちょうど 2 つです。これを $f',f''$ とします。 *$P$ と $C_f$ の辺の両側.* $P$ の各辺は $G$ の閉路 $Q_1\cup P$ に乗るので、 の 1 から両側は相異なる 2 つの面で、どちらも $f$ の中にあるので $f'$ と $f''$ です。$C_f$ の各辺は、$H$ では片側が $f$、もう片側が別の面 $h$ です（$H$ の閉路 $C_f$ に同補題を使う）。$G$ では片側が $h$、もう片側が $f'$ か $f''$ のどちらか一方です。$H$ の $C_f$ に乗らない辺は、$H$ でどちらの側も $f$ でないので、$G$ でも $f',f''$ を側にもちません。 *どちらに属するか.* 閉路 $Z=Q_1\cup P$ に の 1 を使うと、$f'$ と $f''$ は $\mathbb{R}^2\setminus Z$ の異なる成分に含まれます。$Q_2$ から両端を除いた集合は連結で $Z$ と交わらないので、一方の成分 $R$ に含まれます。$f'$ を、$R$ でないほうの成分に含まれる面とします。$Q_2$ の辺 $e$ の内点 $p$ のまわりの円板 $D_p$ は連結で $Z$ と交わらないので $R$ に含まれ、$e$ の両側の面は $D_p$ と交わるので $R$ に含まれます。よって $Q_2$ の辺は $f'$ を側にもたず、$E_{f'}\subseteq E(Q_1)\cup E(P)$ です。 から $E_{f'}$はある閉路の辺をすべて含みますが、$Q_1\cup P$ の中の閉路は $Q_1\cup P$ 自身だけなので、$E_{f'}=E(Q_1)\cup E(P)$ です。 すると $Q_1$ の辺の $f$ 側は $f'$ なので $f''$ ではなく、$Q_2$ の辺の $f$ 側は $f'$ でないので $f''$ です。$P$ の辺は $f''$ を側にもつので、$E_{f''}=E(Q_2)\cup E(P)$ です。 2-連結な平面グラフでは、どの面の境界も閉路である。 $G$ を 2-連結な平面グラフとします。 の $(1)\Rightarrow(3)$ から耳分解 $G_0\subseteq G_1\subseteq\cdots\subseteq G_r=G$ があります。各 $G_i$ は $G$ の一部を取り出した平面グラフで、同定理の $(3)\Rightarrow(1)$ から 2-連結です。$i$ についての帰納法で、$G_i$ のどの面の境界も閉路であることを示します。 $G_0$ は閉路 $C$ です。 から面は内部と外部の 2 つです。 の 1 から、$C$ のどの辺も両側が相異なる面なので、2 つの面はどちらも $C$ のすべての辺を境界にもち、境界は $C$ です。 $G_{i-1}$ で正しければ、 から、$G_i$ の面の境界は、$G_{i-1}$ の面の境界の閉路か、閉路 $Q_1\cup P$、$Q_2\cup P$ のどれかです。 とくに、2-連結な平面グラフでは、どの辺もちょうど 2 つの面の境界に 1 回ずつ現れ、面の次数は境界の閉路の長さです。 ### 4.2. 双対グラフ 平面グラフ $G$ の**双対グラフ** $G^*$ を次で定める。頂点は $G$ の面である。$G$ の各辺 $e$ に対し、$f_1(e)$ と $f_2(e)$ を結ぶ辺 $e^*$ を 1 本置く。$f_1(e)=f_2(e)$（$e$ が橋）のときは $e^*$ は自己ループになり、2 つの面が複数の辺を共有すれば多重辺になる。辺集合 $F\subseteq E(G)$ に対し $F^*=\{e^*:e\in F\}$ と書く。 $G^*$ では、自己ループを長さ 1 の閉路、2 本の多重辺を長さ 2 の閉路と見なします。各面の中に点を 1 つ取り、辺 $e$ をはさんで向かい合う面の点どうしを、$e$ をちょうど 1 回横切る曲線で結ぶと、$G^*$ も平面に描けます（**幾何的双対**）。この節の主張は、上の組合せ的な定義だけから証明します。 $G$ を平面グラフ、$B\subseteq E(G)$ とする。$G$ の 2 つの面が $G-B$ の同じ面に含まれることは、それらが双対の部分グラフ $(V(G^*),B^*)$ の同じ連結成分に属することと同値である。とくに、$G-B$ の面の個数は $(V(G^*),B^*)$ の連結成分の個数に等しい。 $|B|$ についての帰納法です。$B=\varnothing$ なら両辺とも「同じ面である」という意味になります。$B=B'\cup\{e\}$（$e\notin B'$）とし、$B'$ で正しいとします。$G-B=(G-B')-e$ です。$e$ の内点での両側の扇形は $G$ でも $G-B'$ でも同じなので、$G-B'$ での $e$ の両側の面は、$f_1(e)$ を含む面と $f_2(e)$ を含む面です。 の 3 から、$G-B$ の面は、この 2 つをつなげたものと、$G-B'$ のほかの面です。一方、$(V(G^*),B'^*)$ に辺 $e^*$ を足すと、$f_1(e)$ の属する連結成分と $f_2(e)$ の属する連結成分がつながり、ほかは変わりません。帰納法の仮定と合わせて、$B$ でも主張が成り立ちます。$G-B$ のどの面も $G$ の面を少なくとも 1 つ含むので、個数も一致します。 $G$ を連結な平面グラフ、$G^*$ をその双対とする。 1. $G^*$ は連結で、頂点は $f(G)$ 個、辺は $m$ 本である。頂点 $f$ の $G^*$ での次数（自己ループは 2 回数える）は $\deg(f)$ である。 2. $F\subseteq E(G)$ が $G$ の閉路の辺集合であるためには、$F^*$ が $G^*$ の極小な辺カット（除くと非連結になる辺集合で、包含について極小なもの）であることが必要十分である。 3. $T\subseteq E(G)$ が $G$ の全域木の辺集合であるためには、$(E(G)\setminus T)^*$ が $G^*$ の全域木（全頂点を連結し、閉路を含まない辺集合）であることが必要十分である。 4. $F\subseteq E(G)$ が $G$ の極小な辺カットであるためには、$F^*$ が $G^*$ の閉路の辺集合であることが必要十分である。 $E=E(G)$、$V^*=V(G^*)$ と書きます。 **1.** 頂点数、辺数、次数は定義のとおりです。連結性は、 で $B=E$ とすると、$G-E$ は辺のない平面グラフで面は 1 つ（）なので、$(V^*,E^*)=G^*$ の連結成分は 1 つです。 **2.** *閉路ならば極小カット.* $F=E(C)$、$C$ を閉路とします。$G-(E\setminus F)$ は $C$ と孤立点からなり、面は 2 つです（ と の 4）。 から $(V^*,(E\setminus F)^*)$ の連結成分は 2 つで、$F^*$ は辺カットです。$e\in F$ とすると、平面グラフ $(V(G),F\setminus\{e\})$ は森で面は 1 つなので、 から$(V^*,(E\setminus F)^*\cup\{e^*\})$ は連結です。つまり $F^*$ から 1 本でも減らすと辺カットでなくなるので、$F^*$ は極小です。 *極小カットならば閉路.* $F^*$ が辺カットなら、$(V^*,(E\setminus F)^*)$ は非連結で、 から平面グラフ $(V(G),F)$ の面は 2 つ以上です。 から $(V(G),F)$ は閉路 $C$ を含みます。前半から $E(C)^*\subseteq F^*$ は辺カットなので、$F^*$ の極小性から $F=E(C)$ です。 **3.** $B=E\setminus T$ と置きます。 *全域木ならば.* $(V(G),T)$ は森なので面は 1 つで、 から $(V^*,B^*)$ は連結です。$B^*$ が $G^*$ の閉路を含むとし、その上の辺 $e^*$ を取ります。閉路の上の辺を除いても連結性は保たれる（自己ループなら両端が同じ頂点で、そうでなければ閉路の残りの辺が両端を結ぶ道になる）ので、$(V^*,B^*\setminus\{e^*\})$ は連結で、同補題から $(V(G),T\cup\{e\})$ の面は 1 つです。ところが $e\notin T$ の両端は木 $T$ の中で隣接しないので、$T\cup\{e\}$ は閉路を含み（ の 4）、 の 1 から面が 2 つ以上あります。矛盾です。よって $B^*$ は閉路を含みません。 *逆.* $(V^*,B^*)$ が連結で閉路を含まないとします。 から $(V(G),T)$ の面は 1 つなので、 の 1 から $T$ は閉路を含みません。$(V(G),T)$ が非連結だとすると、$G$ は連結なので、$(V(G),T)$ の異なる成分を結ぶ辺 $e\in B$ があります。$T\cup\{e\}$ も森で面は 1 つなので、$(V^*,B^*\setminus\{e^*\})$ は連結です。すると $e^*$ は自己ループであるか、両端が $B^*\setminus\{e^*\}$ の中の道で結ばれるので、$B^*$ が閉路を含むことになり矛盾です。よって $(V(G),T)$ は連結で閉路がなく、$T$ は全域木です。 **4.** 2 つの事実を使います。(i) 連結グラフ $G$ で、辺集合 $F$ がすべての全域木と交わることは、$G-F$ が非連結であることと同値です。$G-F$ が連結ならその全域木（）は $F$ と交わらず、$G-F$ が非連結なら $G$ の全域木は $E\setminus F$ に収まらないからです。(ii) 連結な多重グラフ $G^*$ で、辺集合がある全域木に含まれることは、閉路を含まないことと同値です。全域木の部分集合は閉路を含みません。逆に、閉路を含まない辺集合を含む、閉路を含まない辺集合のうち極大なもの $D^*$ を取ると、$(V^*,D^*)$ が非連結なら、$G^*$ の連結性から異なる成分を結ぶ辺があり、それを足しても閉路はできない（できれば両端が $D^*$ の中の道で結ばれている）ので極大性に反します。よって $D^*$ は全域木です。 3 から、$T\mapsto(E\setminus T)^*$ は $G$ の全域木と $G^*$ の全域木の間の全単射です。$F\cap T\ne\varnothing$ は $F\not\subseteq E\setminus T$、すなわち $F^*\not\subseteq(E\setminus T)^*$ と同じです。したがって $$ F\text{ が }G\text{ のすべての全域木と交わる}\iff F^*\text{ が }G^*\text{ のどの全域木にも含まれない} $$ で、(i) と (ii) から、これは「$G-F$ が非連結 $\iff$ $F^*$ が閉路を含む」を意味します。両辺で包含について極小なものを取れば、$G$ の極小な辺カットと $G^*$ の閉路が対応します（閉路を含む辺集合で極小なものは、閉路の辺集合そのものです）。 2 と 4 は、「閉路」と「極小カット」という言葉を入れ替えると $G$ と $G^*$ が入れ替わることを述べています。これが「双対の双対はもとに戻る」ことの組合せ的な内容です。 連結な平面グラフ $G$ の幾何的双対 $G^*$ を平面グラフ（多重辺と自己ループを許す）として描くと、$G^*$ の各面は $G$ の頂点をちょうど 1 つ含み、$G$ は $G^*$ の幾何的双対になります（$(G^*)^*\cong G$）。この主張は幾何的双対の描画を作る位相的な議論を要するので、この章では定理として扱わず、どの証明にも使いません（参考文献の Bondy–Murty の平面グラフの章、Diestel の第 4 章を見てください）。この章が双対について使うのは、組合せ的な定義から証明した上の命題の 2〜4 だけです。なお、同じ平面的グラフでも描画が違えば双対が同型でないことがあります。3-連結であれば描画は本質的に 1 通りで、双対も 1 つに決まります（第 5 章の Whitney の定理）。 の 3 から、$G$ と $G^*$ の全域木は同数です。頂点 $a,b,c,d$、辺 $ab,bc,cd,da,ac$（四角形と対角線 1 本）のグラフ $G$ を、四角形を凸に、対角線を線分で描きます。面は三角形 $abc$、三角形 $acd$、外面 $o$ の 3 つです。双対 $G^*$ は 3 頂点で、$ac^*$ が 2 つの三角形を結び、$ab^*,bc^*$ が $abc$ と $o$ を、$cd^*,da^*$ が $acd$ と $o$ を結びます。 $G$ の全域木を行列木定理（）で数えます。頂点を $a,c,b,d$ の順に並べると Laplacian は $$ L=\begin{pmatrix}3&-1&-1&-1\\-1&3&-1&-1\\-1&-1&2&0\\-1&-1&0&2\end{pmatrix} $$ で、第 1 行と第 1 列を除いた小行列式は $$ \begin{vmatrix}3&-1&-1\\-1&2&0\\-1&0&2\end{vmatrix}=3\cdot4-(-1)\cdot(-2)+(-1)\cdot2=8 $$ です。$G^*$ の Laplacian は、頂点を $abc,acd,o$ の順に並べて $$ L^*=\begin{pmatrix}3&-1&-2\\-1&3&-2\\-2&-2&4\end{pmatrix} $$ で、第 3 行と第 3 列を除いた小行列式は $3\cdot3-1=8$ です。確かに一致します。 ## 5. 正多面体 凸多面体の頂点と辺のなすグラフは、1 つの面の外から多面体を平面に射影することで、連結な平面グラフとして描けます。[正多面体](/mathematics/hs-geometry/solids-spheres-polyhedra#def-regular-polyhedron)では、どの頂点にも同じ本数の辺が集まり、どの面も同じ角数です。この組合せ的な条件だけで、可能性は 5 通りに絞られます。 $d,k\ge3$ とする。連結な平面グラフで、すべての頂点の次数が $d$、すべての面の次数が $k$ であるものがあれば、$(d,k)$ は $$ (3,3),\ (3,4),\ (4,3),\ (3,5),\ (5,3) $$ のどれかであり、頂点数 $n$、辺数 $m$、面数 $f$ は $(d,k)$ から次の表のとおりに決まる。 | $(d,k)$ | $n$ | $m$ | $f$ | 多面体 | |---|---|---|---|---| | $(3,3)$ | 4 | 6 | 4 | 正四面体 | | $(3,4)$ | 8 | 12 | 6 | 立方体 | | $(4,3)$ | 6 | 12 | 8 | 正八面体 | | $(3,5)$ | 20 | 30 | 12 | 正十二面体 | | $(5,3)$ | 12 | 30 | 20 | 正二十面体 | 握手補題（）から $dn=2m$、面の次数の和から $kf=2m$ です。$n=2m/d$、$f=2m/k$ を Euler の公式（）に代入すると $$ \frac{2m}{d}-m+\frac{2m}{k}=2,\qquad\text{すなわち}\qquad\frac1d+\frac1k=\frac12+\frac1m>\frac12 $$ です。$d\ge4$ かつ $k\ge4$ なら左辺は $1/2$ 以下なので、$d=3$ または $k=3$ です。$d=3$ のとき $1/k>1/6$ から $k\in\{3,4,5\}$、$k=3$ のとき同様に $d\in\{3,4,5\}$ です。これで 5 通りに絞られます。 それぞれについて $1/m=1/d+1/k-1/2$ から $m$ を求めます。$(3,3)$: $1/m=1/6$、$m=6$。$(3,4)$ と $(4,3)$: $1/m=1/12$、$m=12$。$(3,5)$ と $(5,3)$: $1/m=1/30$、$m=30$。$n=2m/d$、$f=2m/k$ から表の値が得られます。 5 通りはすべて実現します。$(3,3)$ は $K_4$ を、三角形の中に 1 点を置いて 3 頂点と結んだ描画です。$(3,4)$ は立方体のグラフ $Q_3$ で、大きい正方形の中に小さい正方形を置き、対応する頂点を結んで描くと、面は内側の正方形、4 つの台形、外面の 6 つで、どれも次数 4 です。 $Q_3$ の双対を見ます。頂点は 6 つの面で、2 つの面が辺を共有するとき隣接します。向かい合う面（内側の正方形と外面、向かい合う台形どうし）だけが隣接しないので、双対は $K_6$ から完全マッチング 3 本を除いたグラフ、すなわち正八面体のグラフ $(4,3)$ です。表で $(d,k)$ と $(k,d)$ を入れ替えると $n$ と $f$ が入れ替わるのは、 の 1 の現れです。同じように正十二面体と正二十面体が互いに双対で、正四面体は自分自身と双対です。 ## 6. 平面的グラフの彩色 グラフ $G$ の **$k$-彩色**とは、写像 $c:V(G)\to\{1,\dots,k\}$ で、隣接するどの 2 頂点 $u,v$ についても $c(u)\ne c(v)$ となるものをいう。$k$-彩色をもつグラフを **$k$-彩色可能**という。 地図の国を頂点、国境を接することを辺とすると平面的グラフになり、隣り合う国を違う色で塗り分ける問題は、このグラフの彩色の問題です。彩色の一般論は [第 6 章](/mathematics/graph-theory/graph-colouring) で扱います。ここでは平面性だけから分かることを示します。 平面的グラフは 6-彩色可能である。 頂点数 $n$ についての帰納法です。$n\le6$ なら頂点ごとに違う色を使えます。$n\ge7$ とします。 から次数 5 以下の頂点 $v$ があります。$G-v$ は平面的なので、帰納法の仮定から 6-彩色をもちます。$v$ の隣接点は 5 個以下なので、6 色のうち隣接点に使われていない色があり、それを $v$ に塗れば $G$ の 6-彩色になります。 色を 1 つ減らすには、次数 5 の頂点の隣接点が 5 色すべてを使っている場合に、色を塗り替えて 1 色空ける工夫が必要です。 平面的グラフは 5-彩色可能である。 証明の方針は、六色定理と同じく次数 5 以下の頂点 $v$ を取り除いて帰納法を使うことです。$v$ の 5 つの隣接点が 5 色すべてを使っていると色が余らないので、色を入れ替えて 1 色空けます。色 1 と 3 の頂点がつながる場合は閉路ができて、その内側と外側に別の色の隣接点が分かれ、もう一方の入れ替えが安全にできます。 頂点数 $n$ についての帰納法です。$n\le5$ なら頂点ごとに違う色を使えばよいので、$n\ge6$ とし、$G$ の描画を固定します。 から次数 5 以下の頂点 $v$ があります。帰納法の仮定から、平面グラフ $G-v$ の 5-彩色 $c$ があります。$v$ の隣接点に現れる色が 4 色以下なら、残りの色を $v$ に塗って終わりです。 以下、$d(v)=5$ で、隣接点の色がすべて異なるとします。 から、$v$ 中心の小さい円板 $D$ の中で $G$ は 5 本の半径です。半径の偏角の順（反時計回り）に、対応する辺の他方の端点を $v_1,v_2,v_3,v_4,v_5$ と名付け、色の番号を付け替えて $c(v_i)=i$ とします。 色 $i,j$ に対し、$G-v$ の色 $i$ または $j$ の頂点が誘導する部分グラフを $H_{ij}$ とします。$H_{ij}$ の連結成分（**Kempe 鎖**）の 1 つの上で色 $i$ と $j$ を入れ替えても、$G-v$ の 5-彩色のままです。入れ替えた成分の中の辺の両端は色 $i,j$ が入れ替わるだけで相異なり、成分の頂点と成分の外の頂点を結ぶ辺の外側の端点は、色が $i$ でも $j$ でもない（$i$ か $j$ なら同じ成分に入る）からです。 **場合 1: $v_1$ と $v_3$ が $H_{13}$ の異なる連結成分に属する.** $v_1$ を含む成分の上で色 1 と 3 を入れ替えます。$v_1$ の色は 3 になり、$v_3$ の色は 3 のまま、$v_2,v_4,v_5$ の色は変わりません。$v$ の隣接点に色 1 がなくなるので、$v$ に色 1 を塗れます。 **場合 2: $v_1$ と $v_3$ が $H_{13}$ の同じ連結成分に属する.** $H_{13}$ の中に $v_1$ から $v_3$ への道 $P$ があります。$P$ に辺 $v_3v$、$vv_1$ を足したものは $G$ の閉路で、これを $C$ とします。$C$ の頂点は、$v$ と、色 1 または 3 の頂点です。 *$v_2$ と $v_4$ は $\mathbb{R}^2\setminus C$ の異なる成分にある.* 円板 $D$ の中で、$C$ は辺 $vv_1$、$vv_3$ に対応する 2 本の半径です。$D\setminus C$ は 2 つの扇形に分かれ、偏角の順から、一方 $\Sigma$ は $vv_2$ の半径を、他方 $\Sigma'$ は $vv_4$ と $vv_5$ の半径を含みます。 から、$v$ は $C$ の内部と外部の両方の閉包に属するので、内部も外部も $D\setminus C=\Sigma\cup\Sigma'$ と交わり、連結な $\Sigma$ と $\Sigma'$ は内部と外部に 1 つずつ含まれます。辺 $vv_2$ から $v$ を除いた集合は連結で、$C$ と交わりません（$vv_2$ は $C$ の辺でなく、$v_2$ は色 2 なので $C$ の頂点でもありません）。この集合は $\Sigma$ と交わるので、$v_2$ は $\Sigma$ を含む成分にあります。同様に $v_4$ は $\Sigma'$ を含む成分にあります。 *$v_2$ と $v_4$ は $H_{24}$ の異なる連結成分に属する.* $H_{24}$ の中に $v_2$ から $v_4$ への道 $Q$ があったとします。$Q$ の頂点は色 2 か 4 なので $C$ の頂点ではなく、$Q$ の辺は $C$ の辺ではありません。よって $Q$ の点集合は $C$ と交わらない連結集合で、$\mathbb{R}^2\setminus C$ の 1 つの成分に含まれます。これは $v_2$ と $v_4$ が異なる成分にあることに反します。 そこで、$H_{24}$ の $v_2$ を含む成分の上で色 2 と 4 を入れ替えます。$v_2$ の色は 4 になり、$v_4$ は別の成分にあるので 4 のまま、$v_1,v_3,v_5$ の色は変わりません。$v$ の隣接点に色 2 がなくなるので、$v$ に色 2 を塗れます。 ### 6.1. 外平面的グラフと美術館定理 平面グラフ $G$ に、すべての頂点を閉包に含む面 $f_0$ があるとき、$G$ を**外平面グラフ**という。外平面グラフとして描けるグラフを**外平面的**という。 外平面的グラフは 3-彩色可能である。 外平面グラフ $G$ とその面 $f_0$ について、頂点数 $n$ についての完全帰納法（）で示します。$n\le3$ なら頂点ごとに違う色を使えます。$n\ge4$ とします。 まず、$G$ の頂点集合の一部が誘導する部分グラフ $G'$ も外平面グラフです。$f_0$ は連結で $G'$ と交わらないので $G'$ のある面 $f_0'$ に含まれ、$G'$ の頂点は $f_0$ の閉包、したがって $f_0'$ の閉包に属するからです。 **場合 A: $G$ が 2-連結でない.** $G$ は非連結であるか、切断点 $v$ をもちます。非連結なら、1 つの連結成分を $G_1$、残りを $G_2$ とします。切断点 $v$ があれば、$G-v$ の 1 つの成分の頂点集合を $Z$ とし、$G_1=G[Z\cup\{v\}]$、$G_2=G-Z$ とします。どちらの場合も、$G_1$ と $G_2$ は頂点数が $n$ より小さい外平面グラフで、共有する頂点は高々 1 個、$G$ の辺はすべて $G_1$ か $G_2$ の辺です。帰納法の仮定からそれぞれ 3-彩色でき、共有する頂点があれば $G_2$ の色の名前を付け替えてその頂点の色をそろえます。合わせたものは $G$ の 3-彩色です。 **場合 B: $G$ が 2-連結.** から $f_0$ の境界は閉路 $C$ で、$f_0$ の閉包はすべての頂点を含むので、$C$ は Hamilton 閉路です。$G=C$ なら、$C$ に沿って色 1, 2 を交互に塗り、$n$ が奇数のときは最後の頂点に色 3 を塗れば 3-彩色です。 $C$ に属さない辺 $uv$ があるとします。$C$ を $u$ と $v$ で 2 本の道 $Q_1,Q_2$ に分けます。$uv$ は $C$ の辺でないので、どちらも内部の頂点をもちます。$f_0$ は平面グラフ $C$ の面でもあります（閉包から $f_0$ を除いた集合が $C$ なので、 の 2 が使えます）。辺 $uv$ の内点は $G$ の面 $f_0$ に属さないので、$C$ のもう 1 つの面に含まれます。 を $H=C$、$P=uv$ に使うと、平面グラフ $C+uv$ の面は、$f_0$ と、境界が $Q_1+uv$ の面 $R_1$ と、境界が $Q_2+uv$ の面 $R_2$ の 3 つです。 $Q_1$ の内部の頂点 $x$ と $Q_2$ の内部の頂点 $y$ を結ぶ $G$ の辺はありません。あったとすると、その内点の全体は連結で $C+uv$ と交わらないので、$C+uv$ の 1 つの面に含まれ、それは $f_0$ ではないので、たとえば $R_1$ です。すると $x,y$ は $R_1$ の閉包に属し、$R_1$ の境界 $Q_1+uv$ の上になければなりませんが、$y$ はその上にありません。 したがって、$G_1=G[V(Q_1)]$、$G_2=G[V(Q_2)]$ と置くと、$G$ の辺はすべて $G_1$ か $G_2$ の辺で、共有する頂点は $u,v$ だけ、どちらも頂点数が $n$ より小さい外平面グラフです。帰納法の仮定からそれぞれ 3-彩色できます。$u$ と $v$ はどちらのグラフでも隣接するので、色が異なります。$G_2$ の色の名前を付け替えて $u,v$ の色を $G_1$ でのものにそろえれば、合わせたものは $G$ の 3-彩色です。 $n\ge3$ とする。平面グラフ $G$ が、外面の境界である Hamilton 閉路 $C$ と何本かの弦からなり、どの内面の境界も長さ 3 の閉路（三角形）であるとする。このとき、$\lfloor n/3\rfloor$ 個以下の頂点からなる集合 $S$ で、どの内面の境界も $S$ の頂点を含むものが存在する。 したがって、対角線で三角形に分割された $n$ 角形の美術館は、$\lfloor n/3\rfloor$ 人以下の警備員を頂点に置けば、内部のすべての点を見張れる。 外面の境界 $C$ がすべての頂点を含むので、$G$ は外平面グラフです。 から 3-彩色 $c$ があります。内面の境界の三角形の 3 頂点は互いに隣接するので、3 色がちょうど 1 回ずつ現れます。3 つの色のうち、その色の頂点の個数が最小のものを選び、その色の頂点の集合を $S$ とします。3 つの個数の和は $n$ なので $|S|\le n/3$、整数なので $|S|\le\lfloor n/3\rfloor$ です。どの三角形にもその色の頂点があります。 後半: 三角形は凸なので、その頂点に立つ警備員は三角形全体を見渡せます。多角形の内部は三角形で覆われているので、$S$ の頂点に警備員を置けば全体を見張れます。 自己交差のない多角形は必ず対角線で三角形に分割できるので、 はすべての多角形に適用できます（三角形分割の存在は初等幾何の事実で、この章では証明しません）。くし形の多角形では $\lfloor n/3\rfloor$ 人が実際に必要です。定理は V. Chvátal, "A combinatorial theorem in plane geometry", *J. Combin. Theory Ser. B* 18 (1975), 39–41 によるもので、3-彩色を使う上の証明は S. Fisk, "A short proof of Chvátal's watchman theorem", *J. Combin. Theory Ser. B* 24 (1978), 374 によります。 ### 6.2. 四色定理 平面的グラフは 4-彩色可能である。 は**主張のみ**で、この章では証明しません。知られている証明は、「どの極大な平面的グラフにも必ず現れる配置」の有限個のリスト（不可避集合）を作り、そのどれもが最小の反例には現れえないこと（可約性）を確かめるという形をしています。リストは数百から千数百個の配置からなり、可約性の確認は計算機による場合分けが本体で、人が読み通せる長さの証明は知られていません。出典は次のとおりです。 - K. Appel, W. Haken, "Every planar map is four colorable. Part I: Discharging", *Illinois J. Math.* 21 (1977), 429–490、および K. Appel, W. Haken, J. Koch, "Part II: Reducibility", 同 491–567。 - N. Robertson, D. Sanders, P. Seymour, R. Thomas, "The four-colour theorem", *J. Combin. Theory Ser. B* 70 (1997), 2–44（配置を 633 個に減らした証明）。 - G. Gonthier, "Formal proof—the four-color theorem", *Notices Amer. Math. Soc.* 55 (2008), 1382–1393（証明支援系 Coq による形式的検証）。 このテーマのほかの章の証明は、四色定理に依存しません。 1879 年に Kempe が発表した「証明」は、 と同じ帰納法です。次数 4 以下の頂点は五色定理の場合 1・2 と同じ議論で処理できます。問題は次数 5 の頂点 $v$ で、隣接点 $v_1,\dots,v_5$ に 4 色が現れる場合です。同じ色が 2 回現れるので、たとえば色が順に $1,2,3,4,2$ だとします。Kempe は次のように論じました。$v_1$ と $v_3$ が色 1・3 の Kempe 鎖でつながり、$v_1$ と $v_4$ も色 1・4 の Kempe 鎖でつながっているとする（そうでなければ入れ替えで色 1 が空く）。前者の鎖は $v_2$ を $v_4$ から隔て、後者の鎖は $v_5$ を $v_3$ から隔てる。そこで、$v_2$ を含む色 2・4 の鎖で 2 と 4 を入れ替え、$v_5$ を含む色 2・3 の鎖で 2 と 3 を入れ替えれば、色 2 が空く。 1890 年に Heawood は、**2 つの入れ替えを両方行うと彩色が壊れることがある**と指摘しました。次の例でそれを確かめます。 頂点 $v,v_1,\dots,v_5,a,b,p$ の 9 頂点と、次の 21 本の辺をもつグラフを考えます。 - $v$ と $v_1,\dots,v_5$ を結ぶ 5 本、五角形 $v_1v_2,\ v_2v_3,\ v_3v_4,\ v_4v_5,\ v_5v_1$、 - $a$ から $v_1,v_5,v_4,p,b$ へ、$b$ から $v_1,v_2,v_3,p$ へ、$p$ から $v_3,v_4$ へ。
v v1: 1 v2: 2 v3: 3 v4: 4 v5: 2 a: 3 b: 4 p: 1
図のとおり平面グラフで、$9$ 頂点、$21=3\cdot9-6$ 辺です。$v$ を除いたグラフの 4-彩色を $$ c(v_1)=1,\ c(v_2)=2,\ c(v_3)=3,\ c(v_4)=4,\ c(v_5)=2,\ c(a)=3,\ c(b)=4,\ c(p)=1 $$ とします（隣接する頂点の色が異なることは、辺を 1 本ずつ見て確かめられます）。$v$ の隣接点には 4 色すべてが現れ、色 2 が $v_2$ と $v_5$ に現れています。 - 色 1・3 の鎖 $v_1,a,p,v_3$ が $v_1$ と $v_3$ をつなぎ、色 1・4 の鎖 $v_1,b,p,v_4$ が $v_1$ と $v_4$ をつないでいます。色 1 を空けることはできません。 - $v_2$ を含む色 2・4 の鎖は $\{v_2,b\}$ です（$v_2$ の隣接点で色 4 のものは $b$ だけ、$b$ の隣接点で色 2 のものは $v_2$ だけ）。$v_4$ を含みません。 - $v_5$ を含む色 2・3 の鎖は $\{v_5,a\}$ です。$v_3$ を含みません。 Kempe の処方どおり、$\{v_2,b\}$ で 2 と 4 を、$\{v_5,a\}$ で 2 と 3 を入れ替えると、$c(v_2)=4$、$c(b)=2$、$c(v_5)=3$、$c(a)=2$ となります。たしかに $v$ の隣接点から色 2 は消えますが、**隣接する $a$ と $b$ がともに色 2** になり、彩色ではなくなります。入れ替えを 1 つずつ行っても救えません。先に $\{v_2,b\}$ を入れ替えると $b$ の色が 2 になり、色 2・3 の鎖は $v_5,a,b,v_3$ と延びて $v_5$ と $v_3$ をつないでしまうからです（先に $\{v_5,a\}$ を入れ替えても、$a$ の色が 2 になり、色 2・4 の鎖が $v_2,b,a,v_4$ と延びて $v_2$ と $v_4$ をつなぎます）。2 本の鎖（色 1・3 と色 1・4）が色 1 の頂点 $p$ を共有して絡み合うことを、Kempe の議論は見落としていました。 このグラフ自体は 4-彩色できます。たとえば $$ c(v)=4,\ c(v_1)=1,\ c(v_2)=2,\ c(v_3)=1,\ c(v_4)=3,\ c(v_5)=2,\ c(a)=4,\ c(b)=3,\ c(p)=2 $$ です。破れているのは定理ではなく、証明の方法です。五色定理の証明では入れ替えが 1 回だけなので、この問題は起きません。 球面に $g$ 個の取っ手を付けた曲面（種数 $g$ の向き付け可能な閉曲面）の上にグラフを交差なしに描き、どの面も円板と同相であるとき、Euler の公式は $n-m+f=2-2g$ に変わります。グラフを描ける曲面の種数の最小値を、そのグラフの**種数**といいます。平面的グラフは種数 0 のグラフです。$K_7$ は平面には描けませんが、トーラス（$g=1$）には、$7-21+14=0$ となる 14 個の三角形の面をもつ形で描けます。そのためトーラス上の地図には 7 色が必要になることがあります。これらは定義と事実の紹介で、この章では使いません。詳しくは参考文献の Mohar–Thomassen を見てください。 ## 7. 演習 $n\ge3$ 頂点の連結な平面グラフで、どの面の次数も 3 であるもの（**三角形分割**）は、辺が $3n-6$ 本、面が $2n-4$ 個であることを示せ。 面の次数の和から $3f=2m$ です。Euler の公式（）$n-m+f=2$ に $f=2m/3$ を代入すると $n-m/3=2$、すなわち $m=3n-6$ です。$f=2m/3=2n-4$ です。 の上界 $3n-6$ は、三角形分割でちょうど達成されます。 $n\ge3$ 頂点の平面的な二部グラフの辺数は $2n-4$ 以下であることを示し、平面的な二部グラフ（頂点は 1 個以上）には次数 3 以下の頂点があることを導け。 閉路を含まなければ森で、$m\le n-1\le2n-4$（$n\ge3$）です。閉路を含むなら、二部グラフは奇閉路を含まない（）ので内周は $g\ge4$ です。 の証明のとおり $(g-2)m\le g(n-2)$ で、$g/(g-2)$ は $g$ について減少するので $m\le\frac42(n-2)=2n-4$ です。 $n\le2$ なら次数は 1 以下です。$n\ge3$ なら、握手補題から次数の和は $2m\le4n-8<4n$ なので、次数が 4 未満の頂点があります。 すべての頂点の次数が 3 以上である連結な平面グラフには、次数が 5 以下の面があることを示せ。 どの面の次数も 6 以上だとします。面の次数の和から $2m\ge6f$、すなわち $f\le m/3$ です。握手補題（）から $2m\ge3n$、すなわち $n\le2m/3$ です。すると $$ n-m+f\le\frac{2m}{3}-m+\frac m3=0 $$ となり、Euler の公式（）$n-m+f=2$ に反します。これは の、頂点と面を入れ替えた主張です。 $K_4$ と $K_{2,3}$ は外平面的でないことを示せ。 どちらも 2-連結です（どの 1 頂点を除いても連結で、頂点は 3 個以上）。外平面グラフとしての描画があるとし、すべての頂点を閉包に含む面を $f_0$ とします。 から $f_0$ の境界は閉路で、すべての頂点を含むので Hamilton 閉路です。 $K_{2,3}$ は頂点が 5 個の二部グラフです。二部グラフの閉路は偶数長（）なので、長さ 5 の閉路である Hamilton 閉路をもちません。矛盾です。 $K_4$ は $n=4$、$m=6$ で、Euler の公式（）から $f=4$ です。$\deg(f_0)=4$ で、ほかの 3 つの面の次数は、 から 3 以上です。面の次数の和は $4+3\cdot3=13$ 以上ですが、これは $2m=12$ でなければなりません。矛盾です。 なお、外平面的であることは $K_4$ と $K_{2,3}$ をマイナーに含まないことと同値です。これは [第 5 章](/mathematics/graph-theory/kuratowski-theorem) で扱います。 ## 参考文献 - R. Diestel, *Graph Theory*, Graduate Texts in Mathematics 173, Springer — 第 4 章（平面グラフ。辺を折れ線に限る扱いはこの本に近い）、第 5 章（彩色）。 - J. A. Bondy, U. S. R. Murty, *Graph Theory*, Graduate Texts in Mathematics 244, Springer, 2008 — 平面グラフと双対の章。 - B. Mohar, C. Thomassen, *Graphs on Surfaces*, Johns Hopkins University Press, 2001 — 平面グラフの位相的な基礎と、曲面上のグラフ。 - P. J. Heawood, "Map-colour theorem", *Quart. J. Pure Appl. Math.* 24 (1890), 332–338. - N. Robertson, D. Sanders, P. Seymour, R. Thomas, "The four-colour theorem", *J. Combin. Theory Ser. B* 70 (1997), 2–44.