Kuratowski の定理：マイナーと平面性の判定

0. この記事の要点

点と線でできた図を、線が途中で交わらないように紙の上に描き直せるか、という問いを扱います。たとえば 3 軒の家と 3 つの設備（水道・ガス・電気）をどの家からどの設備へも線でつなごうとすると、どう工夫しても線が交わってしまいます。この記事は、交わらずに描ける図と描けない図を分ける条件を与え、描けない図には必ず、この家と設備の図か、5 つの点がどれも互いにつながった図が（線の途中に点を足した形で）隠れていることを示します。読み終えると、描けないことの証拠を、有限個の図との比較として示せるようになります。

• グラフ $G$ が平面的であるためには、$K_5$ の細分（辺の途中に頂点を足したもの）も $K_{3,3}$ の細分も部分グラフに含まないことが必要十分です（Kuratowski の定理）。「細分を含まない」を「マイナーに含まない」（辺を縮めたり、辺や頂点を消したりして得られるグラフに含まない）に替えても同じです（Wagner の定理）。
• 証明は 2 段です。第 1 段では、3-連結で $K_5$・$K_{3,3}$ をマイナーに含まないグラフに、辺がすべて線分で面がすべて凸多角形の描画を、頂点数についての帰納法で作ります。帰納法を回すのは「3-連結グラフには、縮約しても 3-連結な辺がある」という補題です。
• 第 2 段では、$K_5$・$K_{3,3}$ の細分を含まないグラフに、その性質を保ったまま辺を足せるだけ足すと 3-連結になることを示し、第 1 段に帰着します。
• 副産物として、平面的グラフは辺をすべて線分にして描けます（Fáry の定理）。
• 3-連結な平面的グラフでは、面の境界は「弦をもたず、取り除いてもグラフが連結なままの閉路」として、描画によらずに決まります（Whitney の一意性定理）。
• すべての頂点を外面の境界に置いて描けるグラフ（外平面的グラフ）は、$K_4$ と $K_{2,3}$ をマイナーに含まないグラフです。

この記事で使う事前知識

• 3-連結: 頂点が 4 個以上あり、どの 2 頂点を取り除いても連結なまま残る、という性質。→ 連結度とネットワークフロー
• 分離集合: 取り除くとグラフが連結でなくなる頂点の集まり。→ 連結度とネットワークフロー
• 内素な道: 同じ 2 頂点を結ぶ道の組で、どの 2 本も端点以外の頂点を共有しないもの。→ 内素な道
• 平面グラフと面: 線が交わらないように平面に描いたグラフと、それが平面を分けてできる領域。→ 平面的グラフ
• 面の境界: 面のふちにあたる、グラフの部分。→ 面の境界
• 閉路: 出発点に戻り、途中で同じ頂点を通らない道。→ 閉路

1. 動機

平面グラフの章では、Euler の公式から $K_5$ と $K_{3,3}$ が平面的でないことを示しました（系 3.4［平面グラフ］）。平面的なグラフの辺の途中に頂点を足しても、辺や頂点を取り除いても平面的なままですから、$K_5$ や $K_{3,3}$ の辺を道に置き換えたもの（細分）を部分グラフに含むグラフも、平面的ではありません。

では逆に、平面的でないグラフには、必ず $K_5$ か $K_{3,3}$ の細分が隠れているのでしょうか。Kuratowski が 1930 年に示したのは、そのとおりだということです。平面に描けない理由は、突き詰めればこの 2 つのグラフしかありません。

この定理が強いのは、「描けない」という、あらゆる描き方についての否定的な主張に、有限の証拠（細分を 1 つ見せれば済む）を与えるからです。平面的であることの証拠は描画 1 つ、平面的でないことの証拠は細分 1 つで、どちらも検算できます。「ある有限個のグラフを含まない」という形の特徴づけは、この章の最後に触れるマイナーの理論の出発点にもなりました。

証明は Thomassen による方法に従います。位相の議論を増やさず、連結度についての組合せ的な補題と、凸多角形についての初等的な幾何だけで進めます。得られる描画が線分だけでできているので、Fáry の定理もついてきます。

2. 準備：記法と平面グラフの事実

グラフは有限・単純・無向とします。記法は道・閉路・木の章のとおりで、$|G|$ は頂点の個数、$N(v)$ は近傍、$d(v)$ は次数、$G-S$ は頂点集合 $S$ を除いたグラフです。$k$-連結・分離集合の定義は 定義 2.1［連結度とネットワークフロー］ に従います。相異なる 2 頂点を結ぶ道の組が内素であるとは、どの 2 本も端点以外に頂点を共有しないことです。

平面グラフは、頂点を平面 $\mathbb{R}^2$ の相異なる点、辺を両端点を結ぶ折れ線の弧として描いたもので、辺の内点は他の辺とも頂点とも交わらないものです（平面グラフの章）。平面グラフとして描けるグラフを平面的といいます。平面グラフ $G$ の点集合（頂点と辺の和集合）も $G$ と書き、$\mathbb{R}^2\setminus G$ の連結成分を面、有界でないただ 1 つの面を外面、それ以外を内面と呼びます。面の境界は、面の閉包から面を除いた集合で、$G$ の部分グラフの点集合です（定義 2.6［平面グラフ］）。すべての頂点を閉包に含む面があるように描けるグラフを外平面的といいます（定義 6.4［平面グラフ］）。

平面グラフの章から使う事実は次の 6 つです。

• 折れ線の閉曲線 $Z$ に対し、$\mathbb{R}^2\setminus Z$ はちょうど 2 つの連結成分（有界な内部と非有界な外部）からなり、どちらの境界も $Z$ 全体である（補題 2.7［平面グラフ］）。
• 閉路に乗る辺は、ちょうど 2 つの面の境界に含まれる（補題 2.10［平面グラフ］）。
• 2-連結な平面グラフの面の境界は閉路である（命題 4.2［平面グラフ］）。
• 連結な平面グラフの頂点・辺・面の個数 $n,m,f$ は $n-m+f=2$ を満たす（定理 3.1［平面グラフ］）。
• 内周 $g$ の平面的グラフの辺の数は $g(n-2)/(g-2)$ 以下である（系 3.3［平面グラフ］）。
• $K_5$ と $K_{3,3}$ は平面的でない（系 3.4［平面グラフ］）。

この章の位相的な議論は、次の 2 つの補題に集約します。

補題 2.1（閉路で囲まれた面）✓

$G$ を平面グラフ、$Z$ を $G$ の閉路とし、$\mathbb{R}^2\setminus Z$ の 2 つの連結成分を $R_0,R_1$ とする。

1. $G$ の面 $f$ の境界が $Z$ ならば、$f=R_0$ または $f=R_1$ である。
2. $R_i$ が $G$ の点を含まなければ、$R_i$ は $G$ の面で、その境界は $Z$ である。

証明（補題 2.1）

1: $f$ は連結で $Z$ と交わらないので、$R_0,R_1$ の一方、たとえば $R_0$ に含まれます。$f$ は開集合です。また $f$ の閉包から $f$ を除いた集合は境界 $Z$ で、$R_0$ と交わらないので、$f$ は $R_0$ の中で閉集合でもあります。$R_0$ は連結で $f\ne\varnothing$ ですから $f=R_0$ です。

2: $R_i$ は連結で $G$ と交わらないので、ある面 $f$ に含まれます。$f$ は連結で $Z\subseteq G$ と交わらないので $\mathbb{R}^2\setminus Z$ の 1 つの連結成分に含まれ、それは $R_i$ を含むので $R_i$ 自身です。よって $f=R_i$ で、その境界は 補題 2.7［平面グラフ］ により $Z$ です。

∎

補題 2.2（3 本の道でできた平面グラフの面）✓

相異なる 2 頂点 $a,b$ を結ぶ内素な 3 本の道 $P_1,P_2,P_3$ の和 $\Theta=P_1\cup P_2\cup P_3$ が平面グラフであるとする。このとき $\Theta$ の面はちょうど 3 つで、その境界は $P_1\cup P_2$、$P_1\cup P_3$、$P_2\cup P_3$ である。

証明（補題 2.2）

$\Theta$ は単純グラフなので、長さ 1 の道は高々 1 本で、どの 2 本の和も閉路です。$\Theta$ の閉路は、ある道の内点（$\Theta$ での次数は 2）を通ればその道全体を含むので、3 本のうち何本かの和です。1 本では閉路にならず、3 本では $a$ の次数が 3 になるので、$\Theta$ の閉路は $P_i\cup P_j$ の 3 つだけです。どの 2 頂点も共通の閉路に乗るので、$\Theta$ は 2-連結です（定理 3.2［連結度とネットワークフロー］）。頂点数を $n'$ とすると辺は $n'+1$ 本なので、定理 3.1［平面グラフ］ から面は $3$ つで、各面の境界は閉路です（命題 4.2［平面グラフ］）。

3 つの面の境界は相異なります。実際、2 つの面が同じ閉路 $P_i\cup P_j$ を境界にもつとすると、残る道 $P_k$ の辺は、残る 1 つの面の境界にしか含まれず、「閉路に乗る辺はちょうど 2 つの面の境界に含まれる」（補題 2.10［平面グラフ］）に反します。閉路は 3 つしかないので、3 つの面の境界は 3 つの閉路をちょうど 1 回ずつ尽くします。

∎

閉路 $Z$ に対し、両端だけが $Z$ の上にあり、$Z$ の辺を使わない長さ 1 以上の道を $Z$-道と呼びます。長さ 1 の $Z$-道は $Z$ の弦です。

次の補題は、閉路 $Z$ の「内側」と「外側」のどちらに $Z$-道を描くか、についての補題です。直感的には、円周上に $p_1,q_1,p_2,q_2$ の順に並ぶ端点をもつ 2 本の道は、同じ側に描くと交わってしまうので、必ず反対の側に描かれる、ということです。

補題 2.3（交差する位置の Z-道は同じ側にない）✓

$G$ を平面グラフ、$Z$ を $G$ の閉路、$P,Q$ を頂点を共有しない 2 本の $Z$-道とする。$P$ の両端を $p_1,p_2$、$Q$ の両端を $q_1,q_2$ とし、$q_1$ と $q_2$ が $Z-\{p_1,p_2\}$ の異なる連結成分に属するとする。このとき、$P$ の内点（端点以外の点）と $Q$ の内点は、$\mathbb{R}^2\setminus Z$ の異なる連結成分に含まれる。

証明（補題 2.3）

$Z$ の $p_1$ から $p_2$ への 2 本の道を $Z_1,Z_2$ とし、$q_1$ が $Z_1$ の内点、$q_2$ が $Z_2$ の内点であるとします。平面グラフ $\Theta=Z\cup P$ を考えます。

$\Theta$ は、$p_1$ と $p_2$ を結ぶ内素な 3 本の道 $Z_1,Z_2,P$ の和です。補題 2.2 により、$\Theta$ の面は、境界が $Z=Z_1\cup Z_2$ の面 $f_0$、$Z_1\cup P$ の面 $f_1$、$Z_2\cup P$ の面 $f_2$ の 3 つです。

補題 2.1 の 1 により、$f_0$ は $\mathbb{R}^2\setminus Z$ の連結成分の 1 つ $R_0$ に等しく、$P$ の内点は $f_0$ にも $Z$ にも属さないので、もう一方の成分 $R_1$ にあります。

$Q$ の内点の全体は連結で、$\Theta$ と交わりません（$Q$ は $P$ と頂点を共有せず、$Z$ とは両端でしか交わらない）。よって 1 つの面に含まれます。それが $f_1$ だとすると、$q_1,q_2$ は $f_1$ の閉包 $f_1\cup Z_1\cup P$ に属し、$P$ の上にはないので、どちらも $Z_1$ の上にあります。これは $q_2$ が $Z_2$ の内点であることに反します。$f_2$ でも同様です。したがって $Q$ の内点は $f_0=R_0$ にあり、$P$ の内点は $R_1$ にあります。

∎

3. 細分・縮約・マイナー

3.1. 定義

定義 3.1（細分・位相的マイナー）↗

グラフ $X$ の各辺 $uv$ を、$u$ と $v$ を結ぶ長さ 1 以上の道で置き換えて得られるグラフを $X$ の細分という。ただし、置き換える道の内点は新しく足す頂点で、異なる辺に対応する道は内点を共有しない。$X$ の細分を総称して $TX$ と書く。$TX$ の中で、もとの $X$ の頂点を分岐点、辺に対応する道を細分された辺という。

グラフ $G$ が $X$ のある細分と同型な部分グラフを含むとき、$X$ は $G$ の位相的マイナーであるといい、「$G$ は $TX$ を含む」と書く。

定義 3.2（縮約・マイナー・禁止マイナー）↗

辺 $e=xy$ の縮約 $G/e$ は、$G$ から $x,y$ を除いて新しい頂点 $v_e$ を足し、$v_e$ を $(N(x)\cup N(y))\setminus\{x,y\}$ の各頂点と隣接させたグラフである（$x$ と $y$ の共通の隣接点への辺は 1 本にまとめる）。

グラフ $X$ が $G$ のマイナーであるとは、互いに交わらない空でない集合 $V_x\subseteq V(G)$（$x\in V(X)$）で、各 $G[V_x]$ が連結で、$xy\in E(X)$ ならば $V_x$ と $V_y$ を結ぶ $G$ の辺があるものが取れることをいう。$V_x$ を枝集合、族 $(V_x)$ を $X$ の模型と呼ぶ。

グラフの族 $\mathcal{P}$ がマイナーで閉じるとは、$G\in\mathcal{P}$ のマイナーがすべて $\mathcal{P}$ に属することをいう。このとき、$\mathcal{P}$ に属さないグラフのうち、マイナーの関係について極小なものを $\mathcal{P}$ の禁止マイナーという。

補題 3.3（マイナーの基本性質）✓

1. $X$ が $Y$ のマイナーで、$Y$ が $G$ のマイナーなら、$X$ は $G$ のマイナーである。
2. $X$ が $G$ のマイナーであるためには、$G$ のある部分グラフから辺の縮約を有限回くり返して $X$ と同型なグラフが得られることが必要十分である。
3. $G$ が $TX$ を含めば、$X$ は $G$ のマイナーである。

証明（補題 3.3）

1: $Y$ の中の $X$ の模型を $(U_x)$、$G$ の中の $Y$ の模型を $(V_y)$ とし、$W_x=\bigcup_{y\in U_x}V_y$ とおきます。$Y[U_x]$ が連結で、$Y$ の各辺に対して対応する枝集合の間に $G$ の辺があり、各 $G[V_y]$ が連結なので、$G[W_x]$ は連結です。$xx'\in E(X)$ なら $U_x$ と $U_{x'}$ の間に $Y$ の辺 $yy'$ があり、$V_y\subseteq W_x$ と $V_{y'}\subseteq W_{x'}$ の間に $G$ の辺があります。$W_x$ たちは互いに交わりません。

2（十分性）: 部分グラフ $H\subseteq G$ は、1 点集合 $V_v=\{v\}$ を枝集合として $G$ のマイナーです。$G/e$（$e=ab$）は、$V_{v_e}=\{a,b\}$ と残りの 1 点集合を枝集合として $G$ のマイナーです。あとは 1 をくり返し使います。

2（必要性）: 模型 $(V_x)$ を取り、各 $G[V_x]$ の全域木 $T_x$（系 4.5［道・閉路・木］）と、$X$ の各辺 $xy$ に対して $V_x$ と $V_y$ を結ぶ辺 $e_{xy}$ を 1 本ずつ選びます。これらの頂点と辺からなる部分グラフを $H$ とします。木の辺の総数についての帰納法で、$H$ から縮約で $X$ が得られることを示します。木の辺がなければ、各 $V_x$ は 1 点で、$H$ は $X$ と同型です。木の辺 $ab\in E(T_x)$ があれば、$H/ab$ では $V_x$ を $(V_x\setminus\{a,b\})\cup\{v_{ab}\}$ に、$T_x$ を $T_x/ab$ に替えると同じ形の構造が得られ（木の辺を縮約したものは木で、枝集合の間の辺は 1 本のままです）、木の辺は 1 本減ります。

3: $TX$ の細分された辺ごとに端点の一方を選び、その道の内点をすべて、選んだ端点の枝集合に入れます。分岐点 $x$ の枝集合 $V_x$ は、$x$ と、$x$ から出る何本かの道の一部からなり、連結です。$xy\in E(X)$ なら、対応する道の最後の辺が $V_x$ と $V_y$ を結びます。

∎

3.2. 平面性はマイナーで保たれる

次の命題の 3（辺を縮約しても平面的）は、描画上で辺の両端点を寄せ合わせて 1 点にしても、ほかの辺とぶつからないことを確かめるものです。証明が長いのは、その「ぶつからない」ことを、辺のまわりの細い帯状の領域と距離を使って確かめるためです。

命題 3.4（平面性は部分グラフ・細分・縮約で保たれる）✓

1. 平面的グラフの部分グラフは平面的である。
2. $X$ が平面的であることと、$X$ の細分が平面的であることは同値である。
3. $G$ が平面的なら、どの辺 $e$ についても $G/e$ は平面的である。

したがって、平面的グラフのマイナーは平面的で、平面的グラフは $K_5$ も $K_{3,3}$ も、マイナーにも位相的マイナーにも含まない。

証明（命題 3.4）

1: 描画から頂点と辺を消せば、部分グラフの描画になります。

2: $X$ の描画で、辺の弧の内点に頂点を置けば、その辺を 2 本に分けた細分の描画になります。くり返せば任意の細分が描けます。逆に細分の描画では、細分された辺をなす弧をつなげたものが 1 本の折れ線の弧で、これを $X$ の辺とすれば $X$ の描画です。

3: $e=xy$ とし、$G$ の描画で $e$ をなす折れ線の線分の本数 $k$ についての帰納法で示します。

$k=1$ の場合. $e$ は線分 $[x,y]$ です。$\delta>0$ に対し $N=\{p\in\mathbb{R}^2:\operatorname{dist}(p,[x,y])\le\delta\}$ とおきます。線分は凸集合なので、$p\mapsto\operatorname{dist}(p,[x,y])$ は凸関数です（$p,p'$ に最も近い $[x,y]$ の点を $c,c'$ とすると、$\lambda p+(1-\lambda)p'$ から点 $\lambda c+(1-\lambda)c'\in[x,y]$ までの距離は $\lambda|p-c|+(1-\lambda)|p'-c'|$ 以下です）。したがって、点 $y$ から出る半直線 $t\mapsto y+tu$（$t\ge0$、$u$ は単位ベクトル）に沿った $g(t)=\operatorname{dist}(y+tu,[x,y])$ は凸で、$g(0)=0$、$t\to\infty$ で $g(t)\to\infty$ です。$g(t_1)=\delta$ となる $t_1>0$ があり、凸性から $0\le t<t_1$ では $g(t)\le(t/t_1)\delta<\delta$、$t>t_1$ では $\delta=g(t_1)\le(t_1/t)g(t)$ より $g(t)>\delta$ です。つまり、$y$ から出る半直線は $N$ の境界 $\partial N=\{g=\delta\}$ とちょうど 1 点で交わり、そこまでは $N$ の内部にあります。$x$ についても同じです。

$x$ に接続する $e$ 以外の辺を $f_1,\dots,f_a$ とし、$f_i$ の最初の線分を $[x,p_i]$、$f_i$ のうち $p_i$ から先の部分を $K_i$ とします。$y$ に接続する $e$ 以外の辺 $h_1,\dots,h_b$ についても、最初の線分 $[y,r_j]$ と残りの部分 $L_j$ を同様に定めます。$x,y$ 以外の頂点と、$x$ にも $y$ にも接続しない辺の和集合を $K_0$ とします。$K_0,K_i,L_j$ はどれもコンパクトで、線分 $[x,y]$ と交わりません（辺どうしは共通の端点でしか交わらず、$K_i$ は $x$ を、$L_j$ は $y$ を含みません）。そこで $\delta$ を、これらと $[x,y]$ との距離のどれよりも小さく取ります。

すると $N$ は $K_0,K_i,L_j$ と交わりません。$p_i\in K_i$ は $N$ の外にあるので、線分 $[x,p_i]$ は $\partial N$ とちょうど 1 点 $q_i$ で交わり、$f_i\cap N=[x,q_i]$ です。同様に $h_j\cap N=[y,s_j]$ となる点 $s_j\in\partial N$ があります。辺どうしは端点以外で交わらないので、点 $q_1,\dots,q_a,s_1,\dots,s_b$ は相異なります。

新しい描画を作ります。$N$ の外は変えず、$N$ の中では、線分 $[x,y]$ と $[x,q_i]$ を消して、線分 $[y,q_i]$（$i=1,\dots,a$）を描きます。$N$ の中に残るのは、点 $y$ から $\partial N$ の相異なる点 $q_i,s_j$ への線分だけです。$y$ から出る半直線は $\partial N$ と 1 点でしか交わらないので、これらの線分は相異なる半直線の上にあり、$y$ 以外で交わりません。また、端点 $q_i,s_j$ を除いて $N$ の内部にあるので、$N$ の外の部分とも交わりません。こうして、$x$ に接続していた辺がすべて $y$ に接続する多重グラフの平面描画が得られます。$x$ と $y$ の共通の隣接点 $u$ への 2 本の辺の一方を消せば、$y$ を $v_e$ と読み替えた $G/e$ の描画です。

$k\ge2$ の場合. $e$ の $x$ 側の最初の折れ点 $b$ に頂点を置いて $e$ を 2 本の辺 $xb$ と $by$ に分けたグラフ $G''$ を考えます（2 により平面描画です）。辺 $xb$ は線分なので、$k=1$ の場合の構成で $G''/xb$ の描画が得られます。$b$ の次数は 2 なので $G''/xb$ は $G$ と同型で（$b$ が $x$ の役をします）、この描画での $e$ は、もとの $e$ から最初の線分を除いた $k-1$ 本の線分からなります。帰納法の仮定から $G/e$ は平面的です。

最後の主張を示します。$G$ が平面的で $X$ がそのマイナーなら、補題 3.3 の 2 により $X$ は $G$ の部分グラフから縮約のくり返しで得られるので、1 と 3 から平面的です。$K_5$ と $K_{3,3}$ は平面的でない（系 3.4［平面グラフ］）ので、$G$ のマイナーではありません。位相的マイナーならマイナーでもある（補題 3.3 の 3）ので、位相的マイナーでもありません。

∎

3.3. マイナーと位相的マイナーの関係

$TX$ を含めば $X$ はマイナーですが、逆は一般には成り立ちません。Petersen グラフは $K_5$ をマイナーに含みますが、最大次数が 3 なので、次数 4 の分岐点を 5 つ必要とする $TK_5$ は含みません（例 3.7）。それでも、$K_5$ と $K_{3,3}$ をまとめて扱えば、2 つの概念は一致します。

次の 2 つの補題のねらいは、マイナーの模型（頂点を寄せ集めた塊の族）から、道だけでできた細分を取り出すことです。そのために、各塊 $V_x$ の中から必要な頂点だけを残した木を取り、外から入ってくる辺をその木の先端につけて数えます。

補題 3.5（枝集合の中の木）✓

$(V_x)$ を $G$ の中の $X$ の模型とし、$X$ の各辺 $xy$ に対して、$V_x$ と $V_y$ を結ぶ $G$ の辺 $e_{xy}$ を 1 本ずつ固定する。このとき、各 $x\in V(X)$ について $G[V_x]$ の部分グラフである木 $T_x$ で、次を満たすものがある。$T_x$ に、$x$ に接続する $X$ の辺 $xy$ に対応する辺 $e_{xy}$ と、その $V_y$ 側の端点（外端と呼ぶ）をすべて付け足したグラフ $T_x^+$ は木で、外端はどれも $T_x^+$ の葉である。さらに $d_X(x)\ge2$ なら、$T_x^+$ の葉は外端だけである。

また、2 頂点以上の木では、葉の個数を $\ell$ とすると

$$\sum_{v:\,d(v)\ge3}\bigl(d(v)-2\bigr)=\ell-2$$

が成り立つ。

証明（補題 3.5）

$e_{xy}$ の $V_x$ 側の端点の全体を $A_x$ とします。$G[V_x]$ は連結なので全域木をもち（系 4.5［道・閉路・木］）、$A_x$ を含む $G[V_x]$ の部分木が存在します（$A_x=\varnothing$ のときは 1 頂点の木を取ります）。そのうち頂点数が最小のものを $T_x$ とします。$T_x$ が 2 頂点以上で、葉 $v$ が $A_x$ に属さなければ、$T_x-v$ も $A_x$ を含む木で、最小性に反します。よって、$T_x$ が 2 頂点以上なら葉はすべて $A_x$ に属します。

$T_x^+$ は、木 $T_x$ に次数 1 の頂点（外端。異なる $y$ の外端は異なる $V_y$ に属するので相異なる）を付け足したものなので木で、外端は葉です。$d_X(x)\ge2$ とします。$T_x$ が 1 頂点なら、その頂点の $T_x^+$ での次数は $d_X(x)\ge2$ です。$T_x$ が 2 頂点以上なら、$T_x$ の葉は $A_x$ に属するので $T_x^+$ では次数 2 以上、葉でない頂点はもともと次数 2 以上です。どちらの場合も、外端以外は葉ではありません。

後半を示します。頂点数 $N\ge2$ の木の辺は $N-1$ 本（定理 4.4［道・閉路・木］）なので、握手補題（補題 2.2［道・閉路・木］）から $\sum_v(d(v)-2)=2(N-1)-2N=-2$ です。連結なので次数 0 の頂点はなく、葉は $-1$、次数 2 の頂点は $0$ を寄与するので、$\sum_{d(v)\ge3}(d(v)-2)-\ell=-2$ です。

∎

補題 3.6（マイナーと位相的マイナー）✓

1. $\Delta(X)\le3$ のとき、$X$ が $G$ のマイナーならば、$G$ は $TX$ を含む。
2. $G$ が $K_5$ をマイナーに含めば、$G$ は $TK_5$ か $TK_{3,3}$ を含む。
3. $G$ が $K_5$ か $K_{3,3}$ をマイナーに含むことと、$G$ が $TK_5$ か $TK_{3,3}$ を含むことは同値である。

証明（補題 3.6）

木について次の事実を使います。木 $T$ の頂点 $b$ から相異なる葉 $\ell_1,\ell_2$ への道が $b$ 以外の頂点 $c$ を共有すれば、$b$ から最も遠い共有点の次数は 3 以上である。 実際、木の中の道は一意（定理 4.4［道・閉路・木］）なので、2 本の道は $b$ からある頂点 $c'$ まで一致し、そこから先は頂点を共有しません。$c'\ne b$ なら、$c'$ には $b$ 側の辺と、$\ell_1$ 側・$\ell_2$ 側の相異なる 2 辺が接続します。

1: 補題 3.5 の木 $T_x$、$T_x^+$ を取り、各 $x$ に頂点 $b_x\in V(T_x)$ を次のように定めます。$d_X(x)=3$ のとき、$T_x^+$ の葉は外端の 3 個だけなので、同じ補題の等式から $\sum_{d\ge3}(d-2)=1$、すなわち次数 3 の頂点がちょうど 1 つあり、他は次数 2 以下です。それを $b_x$ とします（外端は葉なので $b_x\in V(T_x)$ です）。$d_X(x)\le2$ のときは $T_x$ の頂点を任意に 1 つ選んで $b_x$ とします。

$X$ の辺 $xy$ に対し、$T_x^+$ の中で $b_x$ から $e_{xy}$ の外端への道を $P_{x,y}$ とします。$x$ に接続する相異なる辺 $xy,xy'$ について、$P_{x,y}$ と $P_{x,y'}$ は $b_x$ しか共有しません。$d_X(x)=3$ のときは、$b_x$ 以外に次数 3 以上の頂点がないので、冒頭の事実から従います。$d_X(x)=2$ のときは、$T_x^+$ は葉が 2 個で次数 3 以上の頂点をもたない木、すなわち 2 つの外端を結ぶ道で、$P_{x,y}$ と $P_{x,y'}$ はその道を $b_x$ で 2 つに分けたものです。

$Q_{xy}=P_{x,y}\cup P_{y,x}$ は、$b_x$ から $V_x$ の中を通り、辺 $e_{xy}$ を渡り、$V_y$ の中を通って $b_y$ に至る道です。$X$ の相異なる辺に対する $Q$ は、共通の端点 $b_x$ 以外に頂点を共有しません（同じ $V_x$ の中では上で見たとおりで、異なる枝集合は交わりません）。よって $\bigcup Q_{xy}$ に、辺をもたない $x$ の $b_x$ を加えたものは、$b_x$ を分岐点とする $X$ の細分です。

2: $K_5$ の模型 $V_1,\dots,V_5$ と 補題 3.5 の木 $T_i^+$ を取ります。$T_i^+$ の葉は外端の 4 個だけなので $\sum_{d\ge3}(d-2)=2$ で、次数 4 の頂点が 1 つあるか、次数 3 の頂点が 2 つあるかのどちらかです。

すべての $i$ で次数 4 の頂点 $b_i$ がある場合、$b_i$ 以外の頂点の次数は 2 以下なので、$b_i$ から 4 つの外端への道は $b_i$ しか共有しません。1 と同じく $Q_{ij}$ を作れば $TK_5$ が得られます。

ある $i$、たとえば $i=5$ で、$T_5^+$ に次数 3 の頂点が 2 つある場合を考えます。それらを $u,w$ とし、$T_5^+$ の中の $u$ から $w$ への道の、$u$ に接続する辺を $g$ とします。$T_5^+-g$ は 2 つの木に分かれ、$u$ を含むほうを $T'$、$w$ を含むほうを $T''$ とします。$T'$ では $u$ の次数は 2 で、他の頂点の次数は $T_5^+$ でのものと同じです。$T'$ は次数 3 以上の頂点をもたないので、補題 3.5 の等式から葉はちょうど 2 個で、それは $T_5^+$ の葉、すなわち外端です。番号を付け替えて、$T'$ の外端が $V_1,V_2$ に、$T''$ の外端が $V_3,V_4$ に属するとします。

$U'=V(T')\cap V_5$、$U''=V(T'')\cap V_5$ とおきます。木から葉を除いても連結なので、$G[U']$ と $G[U'']$ は連結です。6 つの集合を

$$\{U',\ V_3,\ V_4\},\qquad\{U'',\ V_1,\ V_2\}$$

の 2 組に分けると、異なる組の集合の間には必ず $G$ の辺があります。$U'$ と $U''$ の間には $g$、$U'$ と $V_1,V_2$ の間・$U''$ と $V_3,V_4$ の間には外端への辺、$V_3,V_4$ と $V_1,V_2$ の間には $K_5$ の模型の辺があるからです。これは $K_{3,3}$ の模型です。$\Delta(K_{3,3})=3$ なので、1 から $G$ は $TK_{3,3}$ を含みます。

3: $TK_5$ か $TK_{3,3}$ を含めば、補題 3.3 の 3 からマイナーに含みます。逆に、$K_{3,3}$ をマイナーに含めば 1 から $TK_{3,3}$ を含み、$K_5$ をマイナーに含めば 2 から $TK_5$ か $TK_{3,3}$ を含みます。

∎

例 3.7（Petersen グラフの中の $TK_{3,3}$ と $K_5$）

Petersen グラフの頂点を $0,\dots,9$ とし、外側の五角形 $0\,1\,2\,3\,4$、内側の星形 $5\,7\,9\,6\,8$、スポーク $i\,(i+5)$（$i=0,\dots,4$）を辺とします。15 本の辺は

$$01,\ 12,\ 23,\ 34,\ 40,\quad 57,\ 79,\ 96,\ 68,\ 85,\quad 05,\ 16,\ 27,\ 38,\ 49$$

です。

$TK_{3,3}$. 頂点 $0$ を除くと、$1,4,5$ の次数が 2 になります。$1$ は $2$ と $6$ の間、$4$ は $3$ と $9$ の間、$5$ は $7$ と $8$ の間の内点と見ると、残りの 6 頂点 $2,3,6,7,8,9$ を分岐点とするグラフの「辺」は

$$2\text{–}6,\ 2\text{–}3,\ 2\text{–}7,\quad 3\text{–}9,\ 3\text{–}8,\quad 6\text{–}9,\ 6\text{–}8,\quad 7\text{–}8,\ 7\text{–}9$$

の 9 本です。$A=\{2,8,9\}$、$B=\{3,6,7\}$ とおくと、$2$ の相手は $6,3,7$、$8$ の相手は $3,6,7$、$9$ の相手は $3,6,7$ で、$A$ の各頂点が $B$ の全頂点と結ばれています。つまり Petersen グラフから 1 頂点を除いたものは $K_{3,3}$ の細分で、Petersen グラフは平面的ではありません。

$K_5$ マイナー. 枝集合を $V_i=\{i,i+5\}$（$i=0,\dots,4$）とします。各 $V_i$ はスポークで連結です。$V_i$ と $V_{i+1}$ は外側の辺 $i\,(i+1)$ で、$V_i$ と $V_{i+2}$ は内側の辺 $(i+5)\,(i+7)$ で結ばれています（添字は 5 を法とします）。5 つの枝集合のどの 2 つの間にも辺があるので、$K_5$ はマイナーです。

$TK_5$ は含まない. $TK_5$ の分岐点の次数は 4 ですが、Petersen グラフは 3-正則です。補題 3.6 の 2 が「$TK_5$ か $TK_{3,3}$」としか言えない理由がここにあります。

例 3.8（超立方体 $Q_4$ は平面的でない）

$Q_4$ は頂点が $\{0,1\}^4$ の 16 個、辺が「1 座標だけ異なる 2 頂点」の $16\cdot4/2=32$ 本のグラフです。二部グラフなので奇閉路をもたず（定理 3.3［道・閉路・木］）、内周は 4 です。平面的だとすると、系 3.3［平面グラフ］ から辺は $4(16-2)/(4-2)=28$ 本以下でなければならず、$32>28$ に反します。したがって 定理 6.5 により、$Q_4$ は $TK_5$ か $TK_{3,3}$ を含みます（具体的に見つけるのは 演習 8.1 です）。

4. 3-連結グラフの縮約できる辺

Kuratowski の定理の証明は、頂点数についての帰納法です。帰納法では、小さいグラフに移っても仮定（3-連結性）が保たれなければなりません。それを保証するのが次の補題です。

証明の方針は背理法です。縮約すると 3-連結でなくなる辺ばかりだと仮定すると、どの辺にも 3 頂点の分離集合が付いてきます。その分離集合が生む連結成分のうち最小のものに注目すると、そこからさらに小さい成分が見つかり、最小性に反します。

補題 4.1（縮約できる辺（Thomassen））✓

頂点数が 5 以上の 3-連結グラフ $G$ には、$G/e$ も 3-連結であるような辺 $e$ がある。

証明（補題 4.1）

そのような辺がないと仮定して矛盾を導きます。

手順 1（どの辺も 3 点の分離集合に含まれる）. 辺 $xy$ を任意に取ります。$|G/xy|=|G|-1\ge4$ なので、$G/xy$ が 3-連結でないとは、2 個以下の頂点からなる分離集合 $S$ があることです。

$v_{xy}\notin S$ とすると、$S\subseteq V(G)\setminus\{x,y\}$ で、$G-S$ は $G$ の 3-連結性から連結です。$(G/xy)-S=(G-S)/xy$ で、連結グラフの辺を縮約しても連結です（歩道の中の $x,y$ を $v_{xy}$ に置き換えれば歩道になります）。これは $S$ が分離集合であることに反するので、$v_{xy}\in S$ です。$S=\{v_{xy}\}$ とすると、$G-\{x,y\}=(G/xy)-v_{xy}$ が非連結になり、$G$ の 3-連結性に反します。よって $S=\{v_{xy},z\}$ と書け、$G-\{x,y,z\}=(G/xy)-S$ は非連結です。

以上から、どの辺 $xy$ にも、$\{x,y,z\}$ が $G$ の分離集合になる頂点 $z$ があります。このとき、$x,y,z$ のそれぞれは、$G-\{x,y,z\}$ のどの連結成分にも隣接点をもちます。たとえば $x$ が成分 $C$ に隣接点をもたなければ、$\{y,z\}$ が $C$ を残りから分離し、3-連結性に反するからです。

手順 2（最小の成分を取る）. 辺 $xy$、頂点 $z$、$G-\{x,y,z\}$ の連結成分 $C$ の組のうち、$|C|$ が最小のものを取ります。$z$ は $C$ に隣接点 $v$ をもちます。辺 $zv$ に手順 1 を適用すると、$\{z,v,w\}$ が分離集合になる頂点 $w$ があります。

手順 3（もっと小さい成分が見つかる）. $x,y$ のうち $w$ と異なるものは、$G-\{z,v,w\}$ に残ります（$x,y$ は $z$ とも、$C$ の頂点 $v$ とも異なります）。$x$ と $y$ は隣接するので、両方残る場合も同じ連結成分に属します。$G-\{z,v,w\}$ の連結成分は 2 つ以上あるので、$x$ も $y$ も含まない成分 $D$ があります。

手順 1 の最後の注意から、$v$ は $D$ に隣接点 $u$ をもちます。$v\in C$ の隣接点は $C\cup\{x,y,z\}$ に属し、$D$ は $x,y,z$ を含まないので、$u\in C$ です。$D$ は $G-\{x,y,z\}$ の連結な部分グラフで $C$ と交わるので、$D\subseteq C$ です。一方 $v\in C\setminus D$ ですから $|D|<|C|$ です。辺 $zv$、頂点 $w$、成分 $D$ の組は $|C|$ の最小性に反します。

∎

例 4.2（車輪グラフと $K_{3,3}$）

中心 $h$ と閉路 $v_1v_2\cdots v_nv_1$（$n\ge3$）からなり、$h$ がすべての $v_i$ と隣接するグラフを車輪 $W_n$ といいます（$W_3=K_4$）。$n\ge4$ のとき、スポーク $hv_1$ を縮約すると、新しい頂点は $v_2,\dots,v_n$ のすべてと隣接しますが、外周は $v_1$ を失って道 $v_2v_3\cdots v_n$ になります。このグラフでは $v_2$ の隣接点が新しい頂点と $v_3$ の 2 つしかないので、3-連結ではありません（3-連結なら最小次数は 3 以上です。定理 2.2［連結度とネットワークフロー］）。一方、外周の辺 $v_1v_2$ を縮約すると、新しい頂点は $h,v_3,v_n$ と隣接し、得られるのは $W_{n-1}$ で、これは 3-連結です。縮約できる辺は「ある」のであって、どの辺でもよいわけではありません。

$K_{3,3}$ では、どの辺 $a_1b_1$ を縮約しても、新しい頂点が残りの 4 頂点 $a_2,a_3,b_2,b_3$ のすべてと隣接し、4 頂点は閉路 $a_2b_2a_3b_3$ をなすので、$W_4$ になります。

5. 3-連結の場合：凸な描画を作る

この節の目標は 定理 5.6 です。証明の地図を先に書きます。

• 縮約できる辺 $e=xy$ を取り、$H=G/e$ の凸な描画を帰納法の仮定から得る。
• 縮約でできた頂点 $z$ の隣接点は、$H-z$ のある面の境界の閉路 $C$ に並ぶ。その中で、$x$ の隣接点と $y$ の隣接点がどう並ぶかで 3 通りに分ける。
• 共通の隣接点が 3 個以上なら $TK_5$、$x$ の隣接点 2 個と $y$ の隣接点 2 個が交互に並べば $TK_{3,3}$ が見つかり、仮定に反する。
• 残る場合は、$y$ の隣接点が、$x$ の隣り合う 2 つの隣接点の間にまとまっている。このとき $x$ を $z$ の位置に置き、$y$ を $z$ のすぐ近くの適切な方向に置けば、$G$ の凸な描画になる（補題 5.5）。

縮約でできた頂点を x と y に開くときの 3 つの場合。円は閉路 C、黒丸は x の隣接点、白丸は y の隣接点、二重丸は共通の隣接点。左と中央では辺が交わり、それぞれ K₅・K₃,₃ の細分が現れる。右は交わらずに開ける。

5.1. 狭義凸な多角形

平面の 3 点 $a,b,c$ に対し

$$[a,b,c]=\det(b-a,\ c-a)$$

とおきます。$[a,b,c]>0$ は、$c$ が有向直線 $a\to b$ の左側に厳密にあることと同値です。鏡映 $\rho$ では $[\rho a,\rho b,\rho c]=-[a,b,c]$ です。

定義 5.1（狭義凸の位置・凸な描画）↗

平面の点の巡回列 $(v_1,\dots,v_r)$（$r\ge3$）が狭義凸の位置にあるとは、添字を $r$ を法として読むとき、すべての $i$ とすべての $j\ne i,i+1$ について $[v_i,v_{i+1},v_j]>0$ となることをいう。逆順の列がこの条件を満たすときも、狭義凸の位置にあるという。

平面グラフの描画が凸な描画であるとは、どの辺も線分で、どの面の境界も閉路であり、その閉路の頂点を閉路の順に並べた列が狭義凸の位置にあることをいう。

次の補題は、「狭義凸の位置にある点列」が、ふつうの意味の凸多角形（内側が囲まれ、対角線が内側を通る図形）を定めることを、行列式 $[a,b,c]$ の符号だけで確かめるものです。図の上では明らかな事実ですが、以降の補題で内部や角領域を座標で扱うので、ここで一度証明しておきます。結論の 1〜4 だけ頭に入れておけば、証明を読み飛ばしても先の議論は追えます。

補題 5.2（狭義凸の位置にある点列の定める凸多角形）✓

$(v_1,\dots,v_r)$（$r\ge3$）が狭義凸の位置にあるとする。線分 $[v_i,v_{i+1}]$（$1\le i\le r$。この多角形の辺と呼ぶ）の和集合を $Z$ とし、

$$\Pi=\operatorname{conv}\{v_1,\dots,v_r\}=\Bigl\{\sum_{j=1}^rt_jv_j:\ t_j\ge0,\ \sum_{j=1}^rt_j=1\Bigr\}$$

を凸多角形（凸包）と呼ぶ。巡回列の中で隣り合わない 2 頂点を結ぶ線分を対角線と呼ぶ。

1. $v_1,\dots,v_r$ は相異なり、相異なる 2 本の辺が交わるのは、巡回列で続く 2 本が共通の端点で交わる場合だけである。したがって $Z$ は折れ線の閉曲線である。その内部は $\Pi\setminus Z$、外部は $\mathbb{R}^2\setminus\Pi$ である。すべての $i$ と $j\ne i,i+1$ で $[v_i,v_{i+1},v_j]>0$ となる向きに列を読むとき、$\Pi=\bigcap_i\{p:[v_i,v_{i+1},p]\ge0\}$、$\Pi\setminus Z=\bigcap_i\{p:[v_i,v_{i+1},p]>0\}$ である。
2. 対角線の点は、両端を除いて $Z$ の内部にある。
3. $z=v_i$ とし、巡回列での両隣を $a,b$ とする。$a-z$ と $b-z$ は一次独立である。平面の点を $p=z+\lambda(a-z)+\mu(b-z)$ と書くとき、$p\in\Pi$ ならば $\lambda\ge0$ かつ $\mu\ge0$、$p$ が $Z$ の内部にあれば $\lambda>0$ かつ $\mu>0$ である。$z$ 以外の頂点では $(\lambda,\mu)\ne(0,0)$ である。$\Lambda=\{z+\lambda(a-z)+\mu(b-z):\lambda>0,\ \mu>0\}$ は、半直線 $za,zb$ が平面から切り取る 2 つの開いた角領域のうちの一方で、その開きは $\pi$ 未満、もう一方の開きは $\pi$ より大きい。さらに、ある $\delta>0$ があって、$\Lambda$ の点で $z$ からの距離が $\delta$ 未満のものはすべて $Z$ の内部にある。
4. 凸な描画の面の境界の閉路の点集合を $Z$ とすると（頂点の列は狭義凸の位置にある）、その面が内面ならば面は $Z$ の内部に等しく、外面ならば $Z$ の外部に等しい。

証明（補題 5.2）

列を逆順にしても、$Z$、$\Pi$、辺、対角線、両隣の組 $\{a,b\}$ は変わらず、1 の最後の文以外の主張は列の向きによりません（3 は $a$ と $b$、$\lambda$ と $\mu$ を同時に入れ替えても同じ主張です）。そこで、すべての $i$ と $j\ne i,i+1$ で $[v_i,v_{i+1},v_j]>0$ であると仮定します。添字は $r$ を法として読みます。

$f_i(p)=[v_i,v_{i+1},p]=\det(v_{i+1}-v_i,\ p-v_i)$ とおきます。$f_i$ は $p$ の 1 次式なので、$s+t=1$ のとき $f_i(sp+tq)=sf_i(p)+tf_i(q)$ が成り立ちます（$t_1+\dots+t_r=1$ のときの $f_i(\sum_jt_jv_j)=\sum_jt_jf_i(v_j)$ も同様です）。また $f_i(v_i)=f_i(v_{i+1})=0$ で、仮定からそれ以外の頂点 $v_j$ では $f_i(v_j)>0$ です。$r\ge3$ なので、$i-1,i,i+1$ は $r$ を法として相異なります。次のようにおきます。

$$P=\bigcap_i\{p:f_i(p)\ge0\},\qquad U=\bigcap_i\{p:f_i(p)>0\},\qquad W=\mathbb{R}^2\setminus P=\bigcup_i\{p:f_i(p)<0\}.$$

頂点は相異なる. $j\ne i,i+1$ なら $f_i(v_j)>0=f_i(v_i)$ なので $v_j\ne v_i$ です。$v_i=v_{i+1}$ なら $f_i$ は恒等的に $0$ になり、$f_i(v_{i+2})>0$ に反します。

辺の上での $f_k$ の値. $q=(1-t)v_i+tv_{i+1}$（$0\le t\le1$）を辺 $[v_i,v_{i+1}]$ の点とし、$k\ne i$ とします。$f_k(q)=(1-t)f_k(v_i)+tf_k(v_{i+1})$ で、2 つの項はどちらも $0$ 以上です。$f_k(v_i)=0$ となるのは $i\in\{k,k+1\}$、すなわち（$k\ne i$ なので）$k=i-1$ のときだけで、$f_k(v_{i+1})=0$ となるのは $k=i+1$ のときだけです。$i-1\ne i+1$ なので、両方が $0$ になることはありません。したがって

• $k=i-1$ なら $f_k(q)=tf_k(v_{i+1})$ で、$f_k(q)=0$ となるのは $q=v_i$ のときだけ、
• $k=i+1$ なら $f_k(q)=(1-t)f_k(v_i)$ で、$f_k(q)=0$ となるのは $q=v_{i+1}$ のときだけ、
• それ以外の $k\ne i$ では $f_k(q)>0$

です。とくに $Z\subseteq P$ で、$Z$ のどの点でも少なくとも 1 つの $f_i$ が $0$ になるので $Z\cap U=\varnothing$ です。

辺どうしの交わり. $q$ が相異なる 2 本の辺 $[v_i,v_{i+1}]$ と $[v_k,v_{k+1}]$ の両方に属するとします。$f_k$ は辺 $[v_k,v_{k+1}]$ の上で $0$ なので $f_k(q)=0$ です。上のことから、$k=i-1$ で $q=v_i$ であるか、$k=i+1$ で $q=v_{i+1}$ であるかのどちらかです。どちらも、続く 2 本の辺が共通の端点で交わる場合です。頂点は相異なるので、$Z$ は $v_1,v_2,\dots,v_r,v_1$ の順に線分でつないだ、自分自身と交わらない折れ線の閉曲線です。

$P=U\cup Z$. $U\cup Z\subseteq P$ は済んでいます。$p\in P\setminus U$ とすると、ある $i$ で $f_i(p)=0$ です。$v_{i+1}-v_i\ne0$ で $\det(v_{i+1}-v_i,\ p-v_i)=0$ なので、実数 $t$ があって $p=v_i+t(v_{i+1}-v_i)=(1-t)v_i+tv_{i+1}$ と書けます。$f_{i-1}(p)=tf_{i-1}(v_{i+1})\ge0$ と $f_{i-1}(v_{i+1})>0$ から $t\ge0$、$f_{i+1}(p)=(1-t)f_{i+1}(v_i)\ge0$ と $f_{i+1}(v_i)>0$ から $t\le1$ です。よって $p$ は辺 $[v_i,v_{i+1}]$ の上にあり、$p\in Z$ です。

内部と外部. いま示したことから、$\mathbb{R}^2\setminus Z$ は交わらない 2 つの集合 $U$ と $W$ の和集合です。どちらも開集合です（$f_i$ は連続です）。$U$ は空ではありません。重心 $g=\frac1r\sum_jv_j$ について $f_i(g)=\frac1r\sum_jf_i(v_j)$ で、和の各項は $0$ 以上、$j=i+2$ の項は正だからです。$W$ は空でなく、有界でもありません。$t>0$ のとき $f_1(v_1+t(v_1-v_3))=(1+t)f_1(v_1)-tf_1(v_3)=-tf_1(v_3)<0$ だからです。

補題 2.7［平面グラフ］ から、$\mathbb{R}^2\setminus Z$ の連結成分は、有界な内部と非有界な外部のちょうど 2 つです。連結成分 $R$ は連結で、$R\cap U$ と $R\cap W$ は $R$ を覆う交わらない開集合なので、一方は空です。つまり各成分は $U$ か $W$ のどちらかに含まれます。$U$ も $W$ も空でないので、2 つの成分の一方が $U$ に、他方が $W$ に含まれ、$U$ と $W$ はそれぞれ 1 つの成分に一致します。$W$ は有界でないので外部、$U$ が内部です。とくに $U$ は有界で、$P=U\cup Z$ も有界です。

$\Pi=P$. $p=\sum_jt_jv_j\in\Pi$ なら $f_i(p)=\sum_jt_jf_i(v_j)\ge0$ なので $\Pi\subseteq P$ です。逆を示します。辺の点は 2 頂点の凸結合なので $Z\subseteq\Pi$ です。$p\in U$ とします。$f_1(v_1)=0$ なので $p\ne v_1$ です。$t\ge0$ に対し $g(t)=v_1+t(p-v_1)$ とおき、$T=\{t\ge0:g(t)\in P\}$ とします。$f_k(g(t))=(1-t)f_k(v_1)+tf_k(p)$ は $t$ の 1 次式なので、$T$ は閉集合で、$1\in T$ です。$|g(t)-v_1|=t|p-v_1|$ と $P$ の有界性から $T$ は有界です。そこで $t^*=\max T\ge1$ が取れます。$q=g(t^*)\in P=U\cup Z$ です。$q\in U$ なら、すべての $k$ で $f_k(g(t^*))>0$ なので、連続性から $t^*$ より少し大きい $t$ でもすべての $f_k(g(t))>0$ となり、$t^*$ の最大性に反します。よって $q\in Z$ で、$q=(1-s)v_k+sv_{k+1}$（$0\le s\le1$）と書けます。すると

$$p=\Bigl(1-\frac1{t^*}\Bigr)v_1+\frac1{t^*}q=\Bigl(1-\frac1{t^*}\Bigr)v_1+\frac{1-s}{t^*}v_k+\frac{s}{t^*}v_{k+1}$$

は頂点の凸結合で、$p\in\Pi$ です。以上で $\Pi=P$、$\Pi\setminus Z=U$、$\mathbb{R}^2\setminus\Pi=W$ となり、1 が示されました。

2. $v_i,v_j$ を隣り合わない 2 頂点とします。各 $k$ について $f_k(v_i)\ge0$、$f_k(v_j)\ge0$ です。$f_k$ が $0$ になる頂点は $v_k,v_{k+1}$ だけで、この 2 つは隣り合うので、$f_k(v_i)$ と $f_k(v_j)$ の少なくとも一方は正です。したがって $0<t<1$ のとき $f_k((1-t)v_i+tv_j)=(1-t)f_k(v_i)+tf_k(v_j)>0$ で、対角線の両端以外の点は $U$ に属します。

3. $a=v_{i-1}$、$b=v_{i+1}$ とします。$\Delta=\det(b-z,\ a-z)$ とおくと、

$$[a,z,b]=\det(z-a,\ b-a)=\det(z-a,\ b-z)=\det(b-z,\ a-z)=\Delta$$

です（2 番目の等号は $b-a=(b-z)+(z-a)$ から）。$[a,z,b]=f_{i-1}(v_{i+1})>0$ なので $\Delta>0$ で、$a-z$ と $b-z$ は一次独立です。したがって平面の点 $p$ は $p=z+\lambda(a-z)+\mu(b-z)$ とただ 1 通りに書けて、

$$f_i(p)=\det(b-z,\ p-z)=\lambda\Delta,\qquad f_{i-1}(p)=\det(z-a,\ p-a)=\det(z-a,\ p-z)=\mu\det(z-a,\ b-z)=\mu\Delta$$

です。$p\in\Pi=P$ なら $f_i(p),f_{i-1}(p)\ge0$ なので $\lambda,\mu\ge0$、$p\in U$ なら $\lambda,\mu>0$ です。$(\lambda,\mu)=(0,0)$ となる点は $z$ だけです。

$u(\theta)=(\cos\theta,\sin\theta)$ と書くと $\det(u(\sigma),u(\tau))=\sin(\tau-\sigma)$ です。$b-z=\rho_bu(\beta)$、$a-z=\rho_au(\beta+\theta)$（$\rho_a,\rho_b>0$、$0\le\theta<2\pi$）と表すと、$\Delta=\rho_a\rho_b\sin\theta>0$ から $0<\theta<\pi$ です。$z$ 以外の点 $p=z+\rho u(\beta+s)$（$\rho>0$、$0\le s<2\pi$）について

$$\lambda\Delta=\det(b-z,\ p-z)=\rho_b\rho\sin s,\qquad \mu\Delta=\det(p-z,\ a-z)=\rho\rho_a\sin(\theta-s)$$

です。$\lambda>0$ は $0<s<\pi$ と同値で、このとき $-\pi<\theta-s<\pi$ なので、$\mu>0$ は $s<\theta$ と同値です。よって $\Lambda$ は $0<s<\theta$ を満たす点の全体、すなわち半直線 $zb$ から反時計回りに半直線 $za$ までの開いた角領域で、開きは $\theta<\pi$ です。もう一方の角領域は $\theta<s<2\pi$ で、開きは $2\pi-\theta>\pi$ です。

最後に、$\lambda>0$、$\mu>0$、$\lambda+\mu<1$ とすると、$p=(1-\lambda-\mu)z+\lambda a+\mu b$ で、各 $k$ について

$$f_k(p)=(1-\lambda-\mu)f_k(z)+\lambda f_k(a)+\mu f_k(b)$$

です。係数はすべて正、$f_k(z),f_k(a),f_k(b)$ は $0$ 以上で、$f_k$ が $0$ になる頂点は 2 つだけなので、相異なる 3 頂点 $z,a,b$ のどれかでは正です。よって $f_k(p)>0$ で、$p\in U$ です。$\delta=\Delta/(|a-z|+|b-z|)$ とおきます。$|\det(x,y)|\le|x||y|$ なので、$|p-z|<\delta$ ならば

$$|\lambda|+|\mu|=\frac{|\det(b-z,\ p-z)|+|\det(p-z,\ a-z)|}{\Delta}\le\frac{(|a-z|+|b-z|)\,|p-z|}{\Delta}<1$$

です。したがって $\Lambda$ の点で $z$ からの距離が $\delta$ 未満のものは $U$ に属します。

4. 凸な描画では辺は線分なので、面 $f$ の境界の閉路の点集合は、その頂点の列の定める折れ線の閉曲線 $Z$ です。補題 2.1 の 1 から、$f$ は $Z$ の内部か外部に等しくなります。内部は有界、外部は非有界です。内面は有界なので内部に、外面は非有界なので外部に等しくなります。

∎

補題 5.3（狭義凸の位置は小さな変更で保たれる）✓

$(v_1,\dots,v_r)$ が狭義凸の位置にあり、すべての $i,j\ne i,i+1$ で $[v_i,v_{i+1},v_j]>0$ とする。

1. ある $\varepsilon_0>0$ があって、1 つの頂点 $v_i$ を、$v_i$ からの距離が $\varepsilon_0$ 未満の点に取り替えた列も、同じ不等式を満たす。
2. 連続する 3 頂点を $a,z,b$（この順）とし、ベクトル $d$ が $[a,z,z+d]<0$ かつ $[z,b,z+d]>0$ を満たすとする。このとき、十分小さいすべての $\varepsilon>0$ について、$a$ と $z$ の間に $p=z+\varepsilon d$ を挿入した列 $(\dots,a,p,z,b,\dots)$ は同じ不等式を満たす。
3. $d$ が $[a,z,z+d]>0$ かつ $[z,b,z+d]<0$ を満たすなら、十分小さいすべての $\varepsilon>0$ について、$z$ と $b$ の間に $p=z+\varepsilon d$ を挿入した列 $(\dots,a,z,p,b,\dots)$ は同じ不等式を満たす。

証明（補題 5.3）

1: 条件は、頂点の座標の連続関数についての有限個の狭義の不等式です。1 点を少し動かしても、すべて保たれます。

2: 調べる不等式は「各辺 $s\to t$ について、$s,t$ 以外の頂点が厳密に左側にある」です。$p-z=\varepsilon d$ に注意して、辺ごとに確かめます。

• $p$ を端点としない辺. もとの列の辺のうち $a\to z$ 以外のものです。$p$ 以外の頂点については仮定のとおりです。$p$ については、辺 $z\to b$ では $[z,b,p]=\varepsilon[z,b,z+d]>0$、それ以外の辺 $s\to t$（$z$ を端点としない）では $[s,t,z]>0$ なので、$\varepsilon$ が小さければ $[s,t,p]>0$ です。
• 辺 $a\to p$. $z$ 以外の頂点 $v$（$\ne a,p$）は $[a,z,v]>0$ を満たすので、$\varepsilon$ が小さければ $[a,p,v]>0$ です。$z$ については $[a,p,z]=\det(z-a+\varepsilon d,\ z-a)=\varepsilon\det(d,\ z-a)=-\varepsilon[a,z,z+d]>0$ です。
• 辺 $p\to z$. 頂点 $v\ne p,z$ について $[p,z,v]=\det(-\varepsilon d,\ v-z-\varepsilon d)=\varepsilon\det(v-z,\ d)$ です。補題 5.2 の 3 から $v-z=\lambda(a-z)+\mu(b-z)$（$\lambda,\mu\ge0$、同時には $0$ でない）と書け、$\det(a-z,d)=-[a,z,z+d]>0$、$\det(b-z,d)=[z,b,z+d]>0$ なので、$\det(v-z,d)>0$ です。

3: 鏡映 $\rho$ で写し、列を逆順にします。$[\rho s,\rho t,\rho v]=-[s,t,v]$ なので、逆順の列 $(\dots,\rho b,\rho z,\rho a,\dots)$ は定義の不等式を満たします。$\rho b,\rho z,\rho a$ を 2 の $a,z,b$ とし、$\rho d$ を $d$ として 2 を適用します。必要な条件は $[\rho b,\rho z,\rho z+\rho d]<0$ と $[\rho z,\rho a,\rho z+\rho d]>0$、すなわち $[b,z,z+d]>0$ と $[z,a,z+d]<0$ で、$[b,z,z+d]=\det(z-b,d)=-[z,b,z+d]$、$[z,a,z+d]=\det(a-z,d)=-[a,z,z+d]$ から、仮定と同値です。得られた列 $(\dots,\rho b,\rho p,\rho z,\rho a,\dots)$ をもう一度鏡映して逆順にすれば、$(\dots,a,z,p,b,\dots)$ が定義の不等式を満たします。

∎

5.2. 頂点のまわりの順序

補題 5.4（閉路上の順序と、頂点のまわりの方向の順序）✓

$H$ を平面グラフ、$z$ をその頂点とし、$z$ に接続する辺はすべて線分であるとする。$C$ を $H-z$ の閉路、$a,b,c,d$ を $C$ の上にある $z$ の相異なる隣接点とする。$c$ と $d$ が $C-\{a,b\}$ の同じ連結成分に属するならば、$z$ から見た $c$ の方向と $d$ の方向は、2 本の半直線 $za,zb$ が平面から切り取る 2 つの開いた角領域のうち、同じほうに入る。

証明（補題 5.4）

$C$ の $a$ から $b$ への 2 本の道のうち、$c,d$ を含まないほうを $R$ とし、閉路 $K=zaRbz$ を考えます。$K$ は折れ線の閉曲線なので、$\mathbb{R}^2\setminus K$ は 2 つの連結成分からなり、どちらの境界も $K$ 全体です（補題 2.7［平面グラフ］）。

$z$ を中心とする十分小さい円板 $B$ は、$K$ と 2 本の半径（線分 $za,zb$ の一部）でしか交わりません（補題 2.4［平面グラフ］ を平面グラフ $K$ に使います）。$B\setminus K$ は 2 つの開いた扇形で、それぞれ連結なので、$\mathbb{R}^2\setminus K$ の 1 つの成分に含まれます。$z$ はどちらの成分の境界にも属するので、どちらの成分も $B$ と交わります。したがって 2 つの扇形は異なる成分に含まれます。

$c$ の方向と $d$ の方向が異なる角領域に入ると仮定します。線分 $zc$ から $z$ を除いた部分は連結で、$K$ と交わりません（$zc$ は $K$ の辺と $z$ でしか交わらず、$c$ は $K$ の上にありません）。$z$ の近くでは一方の扇形に入るので、$c$ はその扇形を含む成分に属します。同様に $d$ はもう一方の扇形を含む成分に属し、$c$ と $d$ は $\mathbb{R}^2\setminus K$ の異なる成分にあります。ところが、$C$ の中の $c$ から $d$ への道で $a,b$ を通らないものは、$K$ と交わらない連結集合で $c$ と $d$ を結びます。これは矛盾です。

∎

5.3. 頂点を 2 点に開く

次の補題は、§5 冒頭の地図の最後の場合にあたります。縮約でできた頂点 $z$ を 2 点 $x,y$ に開き戻すとき、$x$ の隣接点と $y$ の隣接点が $z$ のまわりで混ざっていなければ、$x$ を $z$ の位置に、$y$ を $z$ のすぐ近くに置いて、凸な描画を保てる、という内容です。$y$ を置く方向を角度で選ぶため、証明は場合分けが続きます。

補題 5.5（頂点を開いても凸な描画が作れる場合）✓

グラフ $H$ が凸な描画をもち、$z$ を次数 3 以上の頂点とする。$N(z)=N_x\cup N_y$、$|N_x|\ge2$、$|N_y|\ge2$ とし、$H-z$ に 2 頂点 $x,y$ と辺 $xy$ を足して、$x$ を $N_x$ の各頂点と、$y$ を $N_y$ の各頂点と隣接させたグラフを $G$ とする。次の 2 条件を仮定する。

• $|N_x\cap N_y|\le2$。
• 相異なる 4 頂点 $x',x''\in N_x$、$u,v\in N_y$ で、$z$ から見た $u$ の方向と $v$ の方向が、半直線 $zx',zx''$ の切り取る 2 つの開いた角領域の異なるほうに入るものは存在しない。

このとき $G$ は凸な描画をもつ。

証明（補題 5.5）

$H$ の凸な描画を固定し、その点集合を $D$ と書きます。

手順 0（$z$ のまわりの面）. $z$ の隣接点を $z$ のまわりの反時計回りの順に $u_1,\dots,u_d$（$d\ge3$）とします。$z$ を中心とする小さい円板 $B(z,r)$ は、$D$ と $d$ 本の半径でしか交わらず、残りは $d$ 個の開いた扇形です（補題 2.4［平面グラフ］）。$u_j$ と $u_{j+1}$ の間の扇形は連結なので 1 つの面に含まれ、その面の境界の閉路は、扇形の縁にある辺 $zu_j$ と $zu_{j+1}$ を含みます。閉路が $z$ で使う辺は 2 本なので、この面の境界の多角形で $z$ の両隣は $u_j$ と $u_{j+1}$ です。$d\ge3$ なので、異なる扇形は異なる面に含まれます。この面が内面なら、面は多角形の内部に等しく（補題 5.2 の 4）、多角形の内部は半直線 $zu_j,zu_{j+1}$ の切り取る開き $\pi$ 未満の角領域に含まれるので（同じ補題の 3）、扇形の中心角は $\pi$ 未満です。外面なら、面は多角形の外部に等しく、開き $\pi$ 未満の角領域の点のうち $z$ に十分近いものは多角形の内部にあるので（同じ補題の 3）、扇形はもう一方の角領域に含まれ、中心角は $\pi$ より大きくなります。

手順 1（配置の整理）. $N_x$ の頂点を $z$ のまわりの反時計回りに $x_1,\dots,x_k$（$k\ge2$）とし、半直線 $zx_i$ から $zx_{i+1}$ までの開いた角領域を $W_i$ とします（添字は $k$ を法とします）。2 番目の仮定を $x'=x_i$、$x''=x_{i+1}$ に使うと、$N_y\setminus N_x$ の頂点の方向はすべて同じ $W_i$ に入り、$N_y\setminus N_x\ne\varnothing$ ならば $N_y\cap N_x\subseteq\{x_i,x_{i+1}\}$ です。$N_y\subseteq N_x$ のときは、1 番目の仮定から $|N_y|=2$ で、2 番目の仮定から $N_y$ の 2 頂点は $N_x$ の中で隣り合い、$N_y=\{x_i,x_{i+1}\}$ と書けます。

以下、$z$ を原点とし、半直線 $zx_i$ の方向を角 $0$ として、方向を反時計回りの角 $\theta\in[0,2\pi)$ で表します。$x_{i+1}$ の角を $\psi\in(0,2\pi)$、$N_y\setminus N_x$ の頂点を角の小さい順に $w_1,\dots,w_m$（$m\ge0$）、その角を $0<\theta_1<\dots<\theta_m<\psi$ とします。$w_0=x_i$、$w_{m+1}=x_{i+1}$、$\theta_0=0$、$\theta_{m+1}=\psi$ とおき、$zw_l$ と $zw_{l+1}$ の間の扇形を含む面を $g_l$、その境界の多角形を $\Pi_l$ とします（$0\le l\le m$）。$N_y$ の頂点を取り付け先と呼びます。それは $w_1,\dots,w_m$ と、$x_i,x_{i+1}$ のうち $N_y$ に属するものです。取り付け先の角の最小値を $\theta_L$、最大値を $\theta_R$ とします。$x_i\in N_y$ なら $\theta_L=0$、そうでなければ $\theta_L=\theta_1$ で、$\theta_R$ も同様です。取り付け先は 2 個以上あるので $\theta_L<\theta_R$ です。

手順 2（外面の位置）. 仮定は $x$ と $y$ について対称です（2 番目の仮定は「半直線 $zu,zv$ が $x'$ と $x''$ の方向を分ける」と言っても同じです）。角 $\theta_R$ から反時計回りに角 $\theta_L+2\pi$ までの開いた角領域を $W'$ とします。$N_x\setminus N_y$ の頂点は、$W_i$ の閉包の外にある $x_j$ と、$x_i,x_{i+1}$ のうち $N_y$ に属さないものです。その方向はすべて $W'$ に入り、$N_x\cap N_y$ の頂点は $W'$ の両端にしか現れません。つまり、$x$ と $y$ の役割を入れ替えると、$W_i$ の役をするのは $W'$ です。$W'$ に含まれる扇形の面は、$W_i$ の外の面と、$x_i\notin N_y$ のときの $g_0$、$x_{i+1}\notin N_y$ のときの $g_m$ です。

外面が $g_0,\dots,g_m$ のどれかであるとします。それが $W'$ に含まれなければ、$x$ と $y$ の役割を入れ替えることで、外面は $g_0,\dots,g_m$ に現れなくなります。$W'$ に含まれるのは、「外面が $g_0$ で $x_i\notin N_y$」か「外面が $g_m$ で $x_{i+1}\notin N_y$」の場合だけで、後者は鏡映で前者に移ります。したがって、次の 2 つの場合だけを考えれば十分です。

• 場合 I: $g_0,\dots,g_m$ はすべて内面である。
• 場合 II: $g_0$ が外面で、$x_i\notin N_y$ である（このとき $m\ge1$、$\theta_L=\theta_1>\pi$ で、$g_1,\dots,g_m$ は内面）。

手順 3（$y$ を置く方向）. 角 $\varphi$ を次の開区間から、どの $\theta_l$ とも異なるように選びます。

• 場合 I: $\max(\theta_L,\ \psi-\pi)<\varphi<\min(\theta_R,\ \pi)$。
• 場合 II: $\pi<\varphi<\theta_1$。

場合 I の区間が空でないことを確かめます。$\theta_L<\theta_R$ と $\psi-\pi<\pi$ は済んでいます。$\theta_L<\pi$ は、$\theta_L=0$ なら明らかで、$\theta_L=\theta_1$ なら $g_0$ が内面なので中心角 $\theta_1<\pi$ です。$\psi-\pi<\theta_R$ は、$\theta_R=\psi$ なら明らかで、$\theta_R=\theta_m$ なら $g_m$ が内面なので $\psi-\theta_m<\pi$ です。

どちらの場合も、$0<\varphi<\psi$ で、すべての取り付け先 $q$（角を $\theta(q)$ とする）について

$$|\theta(q)-\varphi|<\pi$$

が成り立ちます。場合 I では $\theta(q)\ge\theta_L\ge0>\varphi-\pi$ と $\theta(q)\le\theta_R\le\psi<\varphi+\pi$ から、場合 II では $\theta(q)\le\psi<2\pi<\varphi+\pi$ と $\theta(q)\ge\theta_1>\varphi>\varphi-\pi$ から従います。

$d=(\cos\varphi,\sin\varphi)$、$p=z+\varepsilon d$ とおき、新しい描画を次のように定めます。$z$ の位置に $x$ を置き、辺 $zw_1,\dots,zw_m$ を消し（$D$ からこれらを除いた点集合を $D'$ とします）、点 $p$ に $y$ を置いて、$p$ と $z$、$p$ と各取り付け先を線分で結びます。$\varepsilon$ は以下の有限個の条件を満たすように小さく取ります。

手順 4（新しい線分は交わらない）. 取り付け先 $q$ を固定し、三角形 $T=\operatorname{conv}\{z,p,q\}$ を考えます。$\varphi\ne\theta(q)$ なので $T$ はつぶれていません。$T$ の点は線分 $[z,q]$ からの距離が $\varepsilon$ 以下です。$D'$ を 3 つに分けて、$T$ との交わりを調べます。

• $z$ にも $q$ にも接続しない辺と、$z,q$ 以外の頂点の和集合は、コンパクトで線分 $[z,q]$（$H$ の辺）と交わらないので、正の距離があります。$\varepsilon$ がそれより小さければ $T$ と交わりません。
• $q$ に接続する $zq$ 以外の辺は、$q$ から $z$ への方向と異なる方向に出る線分です。$T$ は $q$ を頂点とし $q\to z$ の方向を含む角領域に含まれ、その開きは $\varepsilon\to0$ で $0$ に近づくので、$\varepsilon$ が小さければ、これらの辺と $T$ の交わりは $q$ だけです。
• $z$ に接続する $D'$ の辺は $zx_j$ です。$T$ は $z$ を頂点とし、角が $\theta(q)$ と $\varphi$ の間（差は $\pi$ 未満）の方向からなる閉じた角領域に含まれ、この範囲は $[0,\psi]$ に収まります。$x_j$ の角は $0$ か $\psi$ か $[0,\psi]$ の外なので、$zx_j$ が $T$ と $z$ 以外で交わるのは、$q=x_j$ で $zx_j$ が $T$ の辺 $[z,q]$ そのものであるときだけです。

線分 $[p,q]$ は $T$ に含まれ、$z$ を通らず、$[z,q]$ とは $q$ でしか交わりません。よって $[p,q]\cap D'=\{q\}$ です。線分 $[p,z]$ は $B(z,r)$ の中にあり（$\varepsilon<r$）、方向 $\varphi\in(0,\psi)$ は $D'$ の辺の方向ではないので、$[p,z]\cap D'=\{z\}$ です。$p$ から出る 2 本の線分 $[p,q],[p,q']$ が同じ半直線の上にあれば、一方が他方の端点（$D'$ の点）を内点に含むことになり、いま示したことに反します。よって新しい線分どうしは $p$ でしか交わらず、新しい描画は $G$ の、辺がすべて線分の平面描画です。その点集合を $D''$ と書きます。

手順 5（面の候補）. $G$ の閉路を次のように並べます。

• (α) $w_l$ と $w_{l+1}$ がともに取り付け先である $l$（$0\le l\le m$）について、$\Pi_l$ の頂点 $z$ を $p$ に取り替えた閉路。
• (β) $x_i\in N_y$ のとき三角形 $pzx_i$。$x_{i+1}\in N_y$ のとき三角形 $pzx_{i+1}$。
• (γ) $x_i\notin N_y$ のとき、$\Pi_0$ の $w_1$ と $z$ の間に $p$ を挿入した閉路。$x_{i+1}\notin N_y$ のとき、$\Pi_m$ の $z$ と $w_m$ の間に $p$ を挿入した閉路。

取り付け先を角の順に並べると、(α) は隣り合う取り付け先の組ごとに 1 つで $|N_y|-1$ 個、(β) と (γ) は両端に 1 つずつで合わせて 2 個、全部で $|N_y|+1$ 個です。$g_l$ が内面のとき、$\Pi_l$ を反時計回りに読むと $z,w_l,\dots,w_{l+1}$ の順です。

これらが狭義凸の位置にあること. (α) は 補題 5.3 の 1 から、$\varepsilon$ が小さければ成り立ちます。(β) は、$\varphi\ne0,\pi$（$x_i$ の側）、$\varphi\ne\psi,\psi-\pi$（$x_{i+1}$ の側）なので、つぶれていない三角形です。(γ) には同じ補題の 2 と 3 を使います。$u(\theta)=(\cos\theta,\sin\theta)$ と書くと $\det(u(\theta),d)=\sin(\varphi-\theta)$ です。

• 場合 I の $x_i$ の側: $\Pi_0$ で $z$ の前が $a=w_1$、後が $b=x_i$ です。補題の 2 の条件は $[a,z,z+d]=\det(z-w_1,d)<0$ と $[z,b,z+d]=\det(x_i-z,d)>0$、すなわち $\sin(\varphi-\theta_1)>0$ と $\sin\varphi>0$ で、$\theta_1<\varphi<\pi$ から成り立ちます。
• $x_{i+1}$ の側（場合 I・II 共通。$g_m$ は内面）: $\Pi_m$ で $z$ の前が $a=x_{i+1}$、後が $b=w_m$ です。補題の 3 の条件は $\det(z-x_{i+1},d)>0$ と $\det(w_m-z,d)<0$、すなわち $\sin(\varphi-\psi)<0$ と $\sin(\varphi-\theta_m)<0$ です。場合 I では $\psi-\pi<\varphi<\theta_m<\psi$、場合 II では $\psi-\pi<\pi<\varphi<\theta_1\le\theta_m<\psi$ なので、$\varphi-\psi$ も $\varphi-\theta_m$ も $(-\pi,0)$ に入ります。
• 場合 II の $x_i$ の側: $g_0$ は外面で、$\Pi_0$ を反時計回りに読むと $z$ の前が $a=x_i$、後が $b=w_1$ です。補題の 3 の条件は $\det(z-x_i,d)>0$ と $\det(w_1-z,d)<0$、すなわち $\sin\varphi<0$ と $\sin(\varphi-\theta_1)<0$ で、$\pi<\varphi<\theta_1<2\pi$ から成り立ちます。

内側が空であること. 場合 II の $x_i$ の側の (γ) を除く候補 $Z$ について、$Z$ の囲む凸多角形の内部に $D''$ の点がないことを示します。

まず頂点です。$Z$ が $\Pi_l$ から作られていれば、$\operatorname{conv}(Z)$ は $\Pi_l$ の囲む閉じた凸多角形 $\overline\Pi_l$ と $p$ の凸包に含まれ、その点は $\overline\Pi_l$ からの距離が $\varepsilon$ 以下です。$Z$ に乗らない $H$ の頂点 $v\ne z$ は、$\overline\Pi_l$ に属しません（内部は面、境界上の頂点は $\Pi_l$ の頂点です）。$\varepsilon$ をその距離より小さく取れば、$v$ は $\operatorname{conv}(Z)$ に入りません。三角形 $pzx_i$ では、$\overline\Pi_l$ を線分 $[z,x_i]$ に替えて同じ議論をします。$z$ が頂点でない候補は (α) だけです。(α) の $Z$ を反時計回りに読むと $p,w_l,\dots,w_{l+1}$ で、$z$ が内部にあれば $[p,w_l,z]>0$ かつ $[w_{l+1},p,z]>0$ です。計算すると $[p,w_l,z]=-\varepsilon\det(w_l-z,d)$、$[w_{l+1},p,z]=\varepsilon\det(w_{l+1}-z,d)$ なので、$\sin(\varphi-\theta_l)<0$ かつ $\sin(\varphi-\theta_{l+1})>0$ です。$|\theta_l-\varphi|<\pi$、$|\theta_{l+1}-\varphi|<\pi$ と合わせると $\theta_{l+1}<\varphi<\theta_l$ となり、$\theta_l<\theta_{l+1}$ に反します。$p$ はどの候補でも頂点です。以上で、内部に $G$ の頂点はありません。

次に辺です。辺の内点が $Z$ の内部にあるとします。辺は端点を除いて $Z$ と交わらず（平面描画です）、連結なので、端点を除いて $Z$ の内部に含まれ、両端は $Z$ の頂点です。狭義凸なので、この辺は $Z$ の対角線です。$p$ から出る対角線なら、もう一方の端は $Z$ の上にある取り付け先で、$Z$ での $p$ の両隣以外のものです。ところが $\Pi_l$ の上の取り付け先は $w_l,w_{l+1}$ のほかにありません（ほかの取り付け先 $w$ が $\Pi_l$ の上にあれば、$H$ の辺 $zw$ が $\Pi_l$ の対角線になり、内点が面 $g_l$ に入ってしまいます）。$p$ を端点としない対角線は $H$ の辺で、両端が $\Pi_l$ の頂点です。$\Pi_l$ で隣り合わなければ、内点が $g_l$ に入って矛盾します。$\Pi_l$ で隣り合うのに $Z$ で隣り合わないのは、(γ) での $z$ と $w_1$（または $w_m$）だけで、辺 $zw_1$、$zw_m$ は $G$ にはありません。

したがって、補題 2.1 の 2 により、これらの候補の内部はどれも $G$ の面です。

残りの面. $H$ の面のうち $g_0,\dots,g_m$ 以外のもの $g$ を考えます。辺 $zw_l$（$1\le l\le m$）を境界に含む面は、その両側の扇形を含む $g_{l-1}$ と $g_l$ だけです（補題 2.10［平面グラフ］）。したがって $g$ の境界の閉路は辺 $zw_1,\dots,zw_m$ を含まず、$G$ の閉路でもあります（$z$ を $x$ と読みます）。$g$ は $D'\subseteq D$ の点を含みません。$p$ から出る新しい線分は、$D'$ と端点（$z$ または取り付け先）でしか交わらないので、端点を除いた部分は $g$ の境界（$D'$ の部分集合）と交わらない連結集合です。この部分は $p$ を含み、$p$ 自身は $g_0,\dots,g_m$ の扇形か消した辺の上にあって $g$ に属しません。$g$ の境界と交わらない連結集合は $g$ に含まれるか $g$ と交わらないかのどちらかなので、新しい線分は $g$ と交わらず、$g$ は $G$ の面です（補題 2.1 の 2）。

面の個数を数えます。$c=|N_x\cap N_y|$ とすると、$|V(G)|=|V(H)|+1$、$|E(G)|=|E(H)|+1+c$ です。また $H=G/xy$ で、辺を縮約しても連結成分の個数は変わらないので、$G$ と $H$ の連結成分の個数は等しくなります。系 3.2［平面グラフ］ から $G$ の面は $H$ の面より $c$ 個多くなります。$|N_y|=m+c$ です。

• 場合 I: $H$ の面のうち $g_0,\dots,g_m$ 以外の全部と、候補 $m+c+1$ 個が $G$ の面で、合わせて $H$ の面の数より $c$ 個多い。これで $G$ の面をすべて尽くしています。
• 場合 II: $H$ の面のうち $g_0,\dots,g_m$ 以外（すべて内面）と、$x_i$ の側の (γ) を除く候補 $m+c$ 個が $G$ の面で、$G$ の面の数より 1 つ少ない。残る 1 つが外面です。$x_i$ の側の (γ) の閉路 $Z_0$ は、外面の多角形 $\Pi_0$ に $p$ を挿入した狭義凸な多角形で、その凸包は $\overline\Pi_0$ と $p$ を含みます。外面 $g_0$ は $\Pi_0$ の外部 $\mathbb{R}^2\setminus\overline\Pi_0$ に等しく（補題 5.2 の 1 と 4）、$D$ の点を含まないので、$D'\subseteq D$ は $\overline\Pi_0$ に含まれます。新しい線分は $p$ と $\overline\Pi_0$ の点を結ぶので、$D''$ 全体が $\operatorname{conv}(Z_0)$ に含まれます。したがって $Z_0$ の外部は $G$ の点を含まず、補題 2.1 の 2 により境界が $Z_0$ の面、すなわち外面です。

どちらの場合も、$G$ のすべての面の境界は狭義凸の位置にある閉路です。

∎

5.4. 定理

定理 5.6（3-連結グラフの凸な描画）✓

$G$ を 3-連結グラフとする。$G$ が $K_5$ も $K_{3,3}$ もマイナーに含まなければ、$G$ は凸な描画をもつ。とくに $G$ は平面的である。

証明（定理 5.6）

$|G|$ についての帰納法です（定理 3.2［証明の技術］）。3-連結なら $|G|\ge4$ です。

$|G|=4$ のとき. 3-連結なら最小次数が 3 以上（定理 2.2［連結度とネットワークフロー］）なので $G=K_4$ です。3 頂点を $(0,0),(4,0),(0,4)$ に、残りを $(1,1)$ に置いて辺を線分で描けば、面は 3 つの三角形の内部と、外側の三角形の外部で、凸な描画です。

$|G|\ge5$ のとき. 補題 4.1 により、$H=G/e$ が 3-連結であるような辺 $e=xy$ があります。$H$ は $G$ のマイナーなので、$H$ のマイナーは $G$ のマイナーで（補題 3.3）、$H$ も $K_5$・$K_{3,3}$ をマイナーに含みません。帰納法の仮定から $H$ は凸な描画をもちます。縮約でできた頂点を $z$ とし、$N_x=N_G(x)\setminus\{y\}$、$N_y=N_G(y)\setminus\{x\}$ とおくと、$N_H(z)=N_x\cup N_y$ で、$G$ の最小次数は 3 以上なので $|N_x|,|N_y|\ge2$、$H$ の最小次数も 3 以上なので $d_H(z)\ge3$ です。$G$ は、$H$ から 補題 5.5 の操作で得られるグラフです。

閉路 $C$. $H-z$ は 2-連結です（$H$ が 3-連結なので、$H-z$ は 3 頂点以上で、さらに 1 頂点を除いても連結です）。$H$ の描画から $z$ とその辺を除いた $H-z$ の描画で、点 $z$ を含む面を $F$ とすると、その境界は閉路 $C$ です（命題 4.2［平面グラフ］）。$z$ の隣接点 $u$ はすべて $C$ の上にあります。線分 $zu$ から $u$ を除いた部分は連結で、$H-z$ の描画と交わらず、$z$ を含むので $F$ に含まれ、$u$ は $F$ の閉包に属して $F$ には属さないからです。$C$ は $G-\{x,y\}=H-z$ の閉路でもあります。

場合 (a): $|N_x\cap N_y|\ge3$. 共通の隣接点 $u,v,w$ を取ります。$C$ は $u,v,w$ によって 3 本の道に分かれます。これらと、辺 $xy$、$xu,xv,xw$、$yu,yv,yw$ を合わせると、$x,y,u,v,w$ を分岐点とする $K_5$ の細分になります。補題 3.3 の 3 から $K_5$ が $G$ のマイナーになり、仮定に反します。

場合 (b): 交互に並ぶ. 相異なる $x',x''\in N_x$、$u,v\in N_y$ で、$z$ から見た $u$ と $v$ の方向が、半直線 $zx',zx''$ の切り取る異なる角領域に入るものがあるとします。補題 5.4 の対偶から、$u$ と $v$ は $C-\{x',x''\}$ の異なる連結成分に属します。つまり $C$ の上で $x',u,x'',v$ はこの巡回順に並び、$C$ は 4 本の道 $x'Cu$、$uCx''$、$x''Cv$、$vCx'$ に分かれます。これらと、辺 $xy$、$xx',xx''$、$yu,yv$ を合わせると、$\{x,u,v\}$ と $\{y,x',x''\}$ を 2 つの側とする $K_{3,3}$ の細分になります（$x$ は $y,x',x''$ と辺で、$u$ は $y$ と辺で、$x',x''$ と $C$ の道で結ばれ、$v$ も同様です）。これも仮定に反します。

場合 (c): どちらでもない. このとき 補題 5.5 の 2 つの仮定が成り立つので、$G$ は凸な描画をもちます。

∎

注意 5.7（「狭義」を課す理由）

面の多角形の頂点で角がちょうど $\pi$ になることを許すと、頂点を少し動かしただけで凸でなくなることがあり、帰納法の「$y$ を $z$ の近くに置く」操作が正当化できません。狭義凸の位置という開いた条件にしておくことで、補題 5.3 が使えます。3-連結でないグラフでは、狭義の条件を満たす描画がないことがあります（例 6.9）。

6. 一般の場合：辺を足せるだけ足すと 3-連結になる

この節では、$TK_5$ も $TK_{3,3}$ も含まないグラフを Kuratowski 部分グラフをもたないグラフと呼びます。そのようなグラフ $G$ が、隣接しないどの 2 頂点 $a,b$ についても $G+ab$ が $TK_5$ か $TK_{3,3}$ を含むとき、$G$ は辺極大であるといいます。証明の地図は次のとおりです。

• 辺極大なグラフが 3-連結でなければ、2 頂点 $x,y$ で 2 つの部分 $G_1,G_2$ に分かれ、$xy$ は辺で、$G_1,G_2$ も辺極大である（補題 6.3）。
• 帰納法の仮定と前節の定理から、$G_1,G_2$ は凸な描画をもつ。辺 $xy$ の乗る面に頂点を 1 つ足しても平面的である。
• $G_1$ と $G_2$ にまたがる辺 $z_1z_2$ を足すと Kuratowski 部分グラフができるが、それを $G_i$ に頂点を 1 つ足したグラフの中に移せて、矛盾する（補題 6.4）。

細分の一部を辺で置き換える操作を、補題にしておきます。

補題 6.1（細分された辺の一部を辺で置き換える）✓

$K$ を単純グラフ $X$ の細分とし、$P$ を $K$ の中の長さ 2 以上の道で、内点がどれも分岐点でないものとする。$P$ の両端を $u,w$ とし、$g$ を $u$ と $w$ を結ぶ辺とする。このとき $g$ は $K$ の辺ではなく、$K$ から $P$ の内点を除いて辺 $g$ を足したグラフは、同じ分岐点をもつ $X$ の細分である。

証明（補題 6.1）

分岐点でない頂点は、ちょうど 1 本の細分された辺の内点で、その両隣も同じ細分された辺の上にあります。したがって $P$ は、ある細分された辺 $Q$ の一部です。

$g\in E(K)$ と仮定し、$g$ を含む細分された辺を $Q'$ とします。$Q'=Q$ なら、道 $Q$ の中に $P$ と $g$ からなる閉路ができて矛盾です。$Q'\ne Q$ なら、$Q$ と $Q'$ は 2 頂点 $u,w$ を共有します。異なる細分された辺が共有できるのは共通の端点（分岐点）だけで、$X$ は単純グラフなので、異なる 2 辺が共有する端点は高々 1 つです。これも矛盾です。

$g\notin E(K)$ なので、$Q$ の中の $P$ を辺 $g$ に取り替えると、同じ両端をもつ短い道になります。他の細分された辺は変わらないので、得られるグラフは $X$ の細分です。

∎

$K_5$ と $K_{3,3}$ については、次の事実を使います。確かめるのは有限個の場合です。

補題 6.2（$K_5$・$K_{3,3}$ の中の内素な道）✓

1. $K_5$ のどの 2 頂点も、4 本の内素な道で結ばれる。$K_{3,3}$ のどの 2 頂点も、3 本の内素な道で結ばれる。
2. $K_{3,3}$ の頂点の 2 元集合 $\{u,u'\}$ と $\{v,v'\}$ が交わらなければ、一端が $\{u,u'\}$、他端が $\{v,v'\}$ に属する 4 本の道で、どの 2 本も端点以外に頂点を共有せず、内点が $u,u',v,v'$ のどれとも異なるものがある。

細分 $TK_5$、$TK_{3,3}$ の分岐点についても、同じことが成り立つ。

証明（補題 6.2）

$K_{3,3}$ の 2 つの側を $\{a_1,a_2,a_3\}$、$\{b_1,b_2,b_3\}$ とします。

1: $K_5$ の 2 頂点 $s,t$ は、辺 $st$ と、残りの 3 頂点 $r$ ごとの道 $srt$ で結ばれます。$K_{3,3}$ で同じ側の $a_1,a_2$ は 3 本の道 $a_1b_ja_2$（$j=1,2,3$）で、異なる側の $a_1,b_1$ は辺 $a_1b_1$ と道 $a_1b_2a_2b_1$、$a_1b_3a_3b_1$ で結ばれます。

2: 2 つの側を入れ替える対称性と、各側の中での番号の付け替えによって、次の 3 通りに帰着します。

• $\{a_1,a_2\}$ と $\{b_1,b_2\}$: 4 本の辺 $a_1b_1,a_1b_2,a_2b_1,a_2b_2$。
• $\{a_1,a_2\}$ と $\{a_3,b_1\}$: 辺 $a_1b_1$、$a_2b_1$ と、道 $a_1b_2a_3$、$a_2b_3a_3$。
• $\{a_1,b_1\}$ と $\{a_2,b_2\}$: 辺 $a_1b_2$、$b_1a_2$ と、道 $a_1b_3a_2$、$b_1a_3b_2$。

（$\{a_1,b_1\}$ と $\{a_2,a_3\}$ の場合は、2 番目の場合で 2 つの集合の役割を入れ替えたものです。）細分では、各辺を対応する細分された辺に取り替えれば、同じ性質の道が得られます。

∎

補題 6.3（辺極大なグラフは 2 点で貼り合わされている）✓

$G$ を、頂点数 4 以上で Kuratowski 部分グラフをもたない辺極大なグラフとし、3-連結でないとする。このとき、隣接する 2 頂点 $x,y$ と、$G$ の誘導部分グラフ $G_1,G_2$ で、次を満たすものがある。

1. $G=G_1\cup G_2$、$V(G_1)\cap V(G_2)=\{x,y\}$ で、$A_i=V(G_i)\setminus\{x,y\}$ は空でなく、$A_1$ と $A_2$ を結ぶ辺はない。
2. $x$ も $y$ も、$A_1$ と $A_2$ のそれぞれに隣接点をもつ。
3. $G_1$ と $G_2$ は、Kuratowski 部分グラフをもたない辺極大なグラフである。

証明（補題 6.3）

$G$ は頂点数 4 以上で 3-連結でないので、2 個以下の頂点からなる分離集合があります。そのうち最小のものを $S$ とし、$G-S$ の連結成分 $C$ を 1 つ取って、$G_1=G[V(C)\cup S]$、$G_2=G-V(C)$、$A_i=V(G_i)\setminus S$ とおきます。$A_1,A_2$ は空でなく、$A_1$ と $A_2$ を結ぶ辺はありません。$S$ は最小なので、$S$ の各頂点 $s$ は $G-S$ のどの連結成分にも隣接点をもちます（そうでなければ $S\setminus\{s\}$ が分離集合になります）。

$X$ を $K_5$ か $K_{3,3}$ とし、$K$ を $G$ に 1 本の辺 $e$ を足したグラフ $G+e$ の中の $X$ の細分とします。$A_1$ と $A_2$ を結ぶ $G+e$ の道は、$S$ の頂点を内点に含むか、$e$ が $A_1$ と $A_2$ を結ぶ辺であって $e$ を通ります。この「通り道」が合わせて 2 つ以下なら、$K$ の分岐点が $A_1$ と $A_2$ の両方にあることはありません。両方にあれば、補題 6.2 の 1 による 3 本の内素な道が、それぞれ別の通り道を使わなければならないからです。以下、足す辺 $e$ はどれもこの条件を満たします。また、分岐点がすべて $V(G_1)$ にあるとき、$K$ の頂点 $a\in A_2$ は分岐点でなく、$a$ を内点とする細分された辺を $a$ から両方向にたどると、$A_2$ を出るまでの部分は、両端が通り道（$S$ の頂点、または $e$ の $A_1$ 側の端点）にあり内点が $A_2$ に含まれる道になります。これを $A_2$ への寄り道と呼びます。

$S\ne\varnothing$. $S=\varnothing$ とし、$a_1\in A_1$、$a_2\in A_2$ を結ぶ辺 $e$ を足します。辺極大なので $G+e$ は細分 $K$ を含み、$K\not\subseteq G$ なので $e\in E(K)$ です。通り道は $e$ の 1 つだけなので、分岐点はすべて一方の側、たとえば $A_1$ にあります。$a_2$ を通る寄り道は両端が通り道になければなりませんが、通り道は 1 つしかなく、道の両端は異なるので矛盾です。

$|S|\ne1$. $S=\{v\}$ とし、$v$ の隣接点 $v_1\in A_1$、$v_2\in A_2$ を結ぶ辺 $e=v_1v_2$ を足します。$G+e$ の中の細分 $K$ は $e$ を含みます。通り道は $v$ と $e$ の 2 つなので、分岐点はすべて一方の側、たとえば $V(G_1)$ にあります。$A_2$ への寄り道は、両端が $v$ と $v_1$ で、$v_1$ からは辺 $e$ を通って $A_2$ に入る道 $P=v_1v_2\cdots v$ です。$e$ は 1 本しかなく、$e\in E(K)$ なので、寄り道はちょうど 1 本です。補題 6.1 により、$P$ を $G$ の辺 $vv_1$ に取り替えたものは $X$ の細分で、$G_1\subseteq G$ に含まれます。これは $G$ が Kuratowski 部分グラフをもたないことに反します。

$S=\{x,y\}$ で $xy\in E(G)$. $|S|=2$ が分かったので $S=\{x,y\}$ とします。$xy\notin E(G)$ と仮定して $e=xy$ を足すと、$G+e$ の中の細分 $K$ は $e$ を含みます。通り道は $x,y$ の 2 つなので、分岐点はすべて、たとえば $V(G_1)$ にあります。$A_2$ への寄り道があれば、それは $x$ と $y$ を結ぶ長さ 2 以上の道で、補題 6.1 から辺 $xy=e$ は $K$ の辺でないことになり、矛盾です。よって $K\subseteq G_1+e$ です。$A_2$ に含まれる $G-S$ の連結成分を 1 つ取ると、$x$ も $y$ もそこに隣接点をもつので、内点がその成分に含まれる $x$ から $y$ への道 $P'$ があります。$K$ の辺 $e$ を $P'$ に取り替えると、$P'$ の内点は $K$ に現れないので、やはり $X$ の細分で、$G$ に含まれます。矛盾です。したがって $xy\in E(G)$ です。

これで 1 と 2 が示されました。

$G_1,G_2$ は辺極大. $G_1$ は $G$ の部分グラフなので Kuratowski 部分グラフをもちません。$G_1$ の隣接しない 2 頂点を結ぶ辺 $e'$ を足すと、$G+e'$ は細分 $K\ni e'$ を含みます。通り道は $x,y$ の 2 つで、分岐点はすべて $V(G_1)$ にあるか、すべて $V(G_2)$ にあります。

• すべて $V(G_1)$ にある場合。$A_2$ への寄り道は $x$ と $y$ を結ぶ道で、高々 1 本です（2 本あれば、どちらも細分された辺の一部で、同じ細分された辺の中に $x$ から $y$ への部分が 2 つあるか、異なる 2 本の細分された辺が 2 頂点を共有するかになり、補題 6.1 の証明と同じく矛盾します）。あれば $G$ の辺 $xy$ に取り替えます（補題 6.1）。得られる細分は $G_1+e'$ に含まれます。
• すべて $V(G_2)$ にある場合。同様に、$A_1$ への寄り道（$e'$ を含むかもしれません）を辺 $xy$ に取り替えると、$G_2\subseteq G$ に含まれる細分が得られます。寄り道がなければ、$K\subseteq G_2+e'$ で、$e'$ の両端は $V(G_1)\cap V(G_2)=\{x,y\}$ に属することになりますが、$xy$ はすでに辺なので、これは起こりません。どちらにしても $G$ が Kuratowski 部分グラフをもたないことに反するので、この場合は起こりません。

よって $G_1+e'$ は $TK_5$ か $TK_{3,3}$ を含み、$G_1$ は辺極大です。$G_2$ も同様です。

∎

補題 6.4（辺極大なら 3-連結）✓

頂点数 4 以上で Kuratowski 部分グラフをもたない辺極大なグラフは、3-連結である。

証明（補題 6.4）

頂点数 $|G|$ についての帰納法です（定理 4.3［証明の技術］）。

$|G|=4$. $TK_5$ は 5 頂点以上、$TK_{3,3}$ は 6 頂点以上なので、4 頂点のグラフにはどんな辺を足しても Kuratowski 部分グラフはできません。辺極大なら $G=K_4$ で、3-連結です。

$|G|\ge5$. $G$ が 3-連結でないと仮定し、補題 6.3 の $x,y,G_1,G_2,A_1,A_2$ を取ります。

手順 1（$G_i$ に 1 頂点を足したグラフは平面的）. 各 $i$ について、頂点 $z_i\in A_i$ をうまく選ぶと、$G_i$ に新しい頂点 $v_i$ と 3 本の辺 $v_ix,v_iy,v_iz_i$ を足したグラフ $G_i^+$ が平面的になることを示します。$|G_i|=3$ なら、$A_i$ の唯一の頂点 $c$ は $x,y$ の両方と隣接するので $G_i$ は三角形で、$z_i=c$ とすれば $G_i^+=K_4$ は平面的です。$|G_i|\ge4$ なら、$G_i$ は辺極大なので帰納法の仮定から 3-連結で、$TK_5$ も $TK_{3,3}$ も含まないので 補題 3.6 の 3 から $K_5$・$K_{3,3}$ をマイナーに含まず、定理 5.6 により凸な描画をもちます。辺 $xy$ は 2 つの面の境界に含まれる（補題 2.10［平面グラフ］）ので、その少なくとも一方は内面です。その境界の凸多角形の、$x,y$ 以外の頂点を $z_i$ とし、多角形の内部に点 $v_i$ を取って $x,y,z_i$ と線分で結びます。3 本の線分は凸多角形の内部（面）を通り、$v_i$ でしか交わらないので、$G_i^+$ の平面描画が得られます。

命題 3.4 により、$G_i^+$ も、$G_i^+$ から辺 $v_ix$ または $v_iy$ を縮約したグラフ（$G_i$ に辺 $xz_i$ または $yz_i$ を足したもの）も、Kuratowski 部分グラフをもちません。

手順 2（またぐ辺を足す）. $z_1$ と $z_2$ は隣接しないので、辺極大性から $G+z_1z_2$ は $K_5$ か $K_{3,3}$ の細分 $K$ を含み、$e=z_1z_2\in E(K)$ です。$A_1$ と $A_2$ を結ぶ $G+e$ の道は、$x$ か $y$ を内点に含むか、$e$ を通ります。通り道は 3 つです。$A_i$ にある分岐点の個数を $\beta_i$ とします。

$K$ が $TK_5$ のとき、$\beta_1\ge1$ かつ $\beta_2\ge1$ なら、補題 6.2 の 1 の 4 本の内素な道が別々の通り道を使うことになり、矛盾です。$K$ が $TK_{3,3}$ のとき、$\beta_1\ge2$ かつ $\beta_2\ge2$ なら、同じ補題の 2 の 4 本の道（端点は $A_1\cup A_2$ にあるので通り道の頂点 $x,y$ ではなく、内点は互いに共有されません）が別々の通り道を使うことになり、矛盾です。したがって、番号を付け替えれば、次のどちらかです。

• 場合 A: $\beta_2=0$。
• 場合 B: $K$ は $TK_{3,3}$ で、$\beta_2=1$。

場合 A. $K$ の頂点で $A_2$ にあるものは分岐点でなく、補題 6.3 の証明と同じく、$A_2$ への寄り道（内点が $A_2$ に含まれ、両端が $x,y,z_1$ のうちの 2 つである道。$z_1$ を端とするものは辺 $e$ から始まる）の内点です。同じ 2 頂点を両端とする寄り道は 2 本なく、$z_1$ を端とするものは $e$ を使うのでちょうど 1 本です。その他方の端が $x$ であるとします（$y$ のときも同様です）。この寄り道を辺 $z_1x$ に、$x$ と $y$ を結ぶ寄り道があればそれを辺 $xy$ に取り替えると、補題 6.1 により、$G_1$ に辺 $xz_1$ を足したグラフに含まれる細分が得られます。これは手順 1 に反します。

場合 B. $A_2$ にある唯一の分岐点を $v$ とします。$v$ から出る 3 本の細分された辺は、他端の分岐点が $V(G_1)$ にあるので $A_2$ を出ます。それぞれについて、$v$ から見て最初に $A_2$ の外に出る頂点は $x$、$y$、または（$e$ を渡って）$z_1$ で、3 本は $v$ 以外で交わらないので、この 3 頂点がちょうど 1 回ずつ現れます。$K$ のうち $A_2$ にある残りの頂点は分岐点でなく、$e$ はすでに使われているので、$x$ と $y$ を結ぶ寄り道の内点です。

$K$ から $A_2$ の頂点をすべて除き、新しい頂点 $v_1$ と辺 $v_1x,v_1y,v_1z_1$ を足し、$x$ と $y$ を結ぶ寄り道があれば辺 $xy$ を足します（補題 6.1）。$v$ から $x,y,z_1$ までの 3 本の道が 3 本の辺に置き換わっただけなので、得られるグラフは $v_1$ を分岐点の 1 つとする $K_{3,3}$ の細分で、$G_1^+$ に含まれます。これも手順 1 に反します。

どちらの場合も矛盾するので、$G$ は 3-連結です。

∎

定理 6.5（Kuratowski の定理）✓

グラフ $G$ について、次は同値である。

1. $G$ は平面的である。
2. $G$ は $K_5$ の細分も $K_{3,3}$ の細分も部分グラフに含まない。

証明（定理 6.5）

$(1)\Rightarrow(2)$ は 命題 3.4 です。

$(2)\Rightarrow(1)$. $|G|\le3$ なら $G$ は $K_3$ の部分グラフで、三角形として描けます。$|G|\ge4$ とします。$G$ に、Kuratowski 部分グラフができない限り辺を足し続けます。辺の数は有限なので、この操作は止まり、$G$ を全域部分グラフとして含む辺極大なグラフ $G'$ が得られます。補題 6.4 により $G'$ は 3-連結で、補題 3.6 の 3 により $K_5$ も $K_{3,3}$ もマイナーに含みません。定理 5.6 から $G'$ は凸な描画をもち、平面的です。その部分グラフ $G$ も平面的です（命題 3.4 の 1）。

∎

系 6.6（Wagner の定理）✓

グラフ $G$ が平面的であるためには、$K_5$ も $K_{3,3}$ も $G$ のマイナーでないことが必要十分である。

証明（系 6.6）

補題 3.6 の 3 により、「$K_5$ も $K_{3,3}$ もマイナーでない」は「$TK_5$ も $TK_{3,3}$ も含まない」と同値で、後者は 定理 6.5 により平面的であることと同値です。

∎

系 6.7（Fáry の定理）✓

平面的グラフは、辺がすべて線分である平面描画をもつ。

証明（系 6.7）

$|G|\le3$ なら、頂点を一直線上にない点に置いて辺を線分で描けます。$|G|\ge4$ のとき、定理 6.5 の $(2)\Rightarrow(1)$ の証明で得た $G'$ の凸な描画は、辺がすべて線分です。$G$ は $G'$ の全域部分グラフなので、$G$ に無い辺を消せば $G$ の描画になります。

∎

命題 6.8（三角形分割への埋め込み）✓

頂点数 4 以上の平面的グラフ $G$ に対し、$G$ を全域部分グラフとして含むグラフ $G'$ と、$G'$ の凸な描画で、内面の境界がすべて長さ 3 の閉路であるものが存在する。

証明（命題 6.8）

定理 6.5 の証明の $G'$ と、その凸な描画を取ります。内面の境界の凸多角形 $\Pi$ が 4 頂点以上をもつとし、$\Pi$ で隣り合わない 2 頂点 $u,v$ を取ります。$uv\in E(G')$ なら、辺 $uv$ は線分で $\Pi$ の対角線なので、内点が $\Pi$ の内部、すなわち面に入ってしまいます（補題 5.2 の 2 と 4）。よって $uv\notin E(G')$ です。このとき対角線 $[u,v]$ を描き足せば $G'+uv$ の平面描画になるので、$G'+uv$ は平面的で、命題 3.4 から Kuratowski 部分グラフをもちません。これは $G'$ の辺極大性に反します。したがって内面の境界はすべて三角形です。

∎

Fáry の定理には、極大平面グラフ（三角形分割）から次数 5 以下の頂点を除いて帰納法を回す、Kuratowski の定理を経由しない古典的な証明もあります。ここでは、3-連結の場合の定理が線分による描画を直接与えるので、系として得られました。命題 6.8 は彩色の章で、平面的グラフのリスト彩色に使います。

例 6.9（$K_{3,3}$ から 1 辺を除いたグラフ）

$K_{3,3}$ から辺 $a_3b_3$ を除いたグラフ $G$ を考えます。$a_3$ の隣接点は $b_1,b_2$、$b_3$ の隣接点は $a_1,a_2$ です。頂点を

$$a_3=(3,0),\quad b_1=(0,3),\quad a_1=(-3,0),\quad b_2=(0,-3),\quad a_2=(-1,0),\quad b_3=(-2,0)$$

に置き、8 本の辺を線分で描くと、辺は交わりません。面は 4 つで（$n-m+f=6-8+4=2$）、境界は

• 外面: $a_3b_1a_1b_2$（正方形）、
• $a_3b_1a_2b_2$（凧形で、狭義凸の位置）、
• $b_1a_1b_3a_2$ と $a_1b_2a_2b_3$

です。最後の 2 つでは $a_1,b_3,a_2$ が一直線上に並び、$b_3$ での角が $\pi$ になります。図形としては三角形で凸ですが、狭義凸の位置ではありません。

これは避けられません。$b_3$ の次数は 2 なので、$b_3$ を通る面は 2 つで、$b_3$ での 2 つの角の和は $2\pi$ です。両方が内面なら、少なくとも一方の角は $\pi$ 以上になります。一方を外面にすれば $b_3$ は救えますが、$a_3$ も次数 2 で同じ事情にあり、両方を外面の境界に置くには、外面の境界が $b_1a_3b_2$ と $a_1b_3a_2$ をともに含む閉路、すなわち 6 頂点すべてを通る $a_3b_1a_1b_3a_2b_2$ か $a_3b_1a_2b_3a_1b_2$ でなければなりません。前者では残る 2 辺 $a_1b_2$ と $a_2b_1$ が、後者では $a_1b_1$ と $a_2b_2$ が、閉路の上で端点が交互に並ぶ弦なので、補題 2.3 により、ともに内部に描くことはできません。$G$ は 3-連結でない（$\{b_1,b_2\}$ が $a_3$ を切り離す）ので、定理 5.6 と矛盾はしません。

注意 6.10（グラフマイナー定理）

Wagner の定理は、「平面的」というマイナーで閉じた性質が、有限個（2 個）の禁止マイナーで特徴づけられることを述べています。Wagner は、マイナーで閉じたどんなグラフの族にも有限個の禁止マイナーしかないだろうと予想しました。これは Robertson と Seymour が連作論文 “Graph minors”（第 1 論文は 1983 年、予想を証明した第 20 論文は 2004 年）で証明し、グラフマイナー定理と呼ばれています。同じことですが、「有限グラフの無限列 $G_1,G_2,\dots$ には、$G_i$ が $G_j$ のマイナーになる $i<j$ が必ずある」という主張です。証明は連作全体で数百ページに及び、この章の範囲を大きく超えるので、ここでは主張だけを紹介します。本テーマの定理の証明には使いません。出典は参考文献の Robertson–Seymour の論文と、Diestel の教科書の第 12 章です。

7. 描画の一意性と外平面的グラフ

7.1. Whitney の一意性定理

平面的グラフの描画は一般には何通りもあり、どの閉路が面の境界になるかも描画によって変わります（例 7.2）。3-連結なら、そうはなりません。

定理 7.1（Whitney の一意性定理）✓

$G$ を 3-連結な平面グラフ、$C$ を $G$ の閉路とする。$C$ が $G$ のある面の境界であるためには、次の 2 つが成り立つことが必要十分である。

1. $C$ は弦をもたない（$C$ は誘導部分グラフである）。
2. $G-V(C)$ は連結である。

とくに、3-連結な平面的グラフでは、どの閉路が面の境界になるかは描画によらない。

証明（定理 7.1）

$\mathbb{R}^2\setminus C$ の 2 つの連結成分を $R_0,R_1$ とします。

十分性. 1 と 2 を仮定します。$G-V(C)$ が空なら、1 から $G=C$ となり、3-連結であることに反します。$G-V(C)$ は空でない連結グラフなので、その点集合は連結で、$C$ と交わらず、$R_0,R_1$ の一方、たとえば $R_1$ に含まれます。$C$ の辺でない $G$ の辺は、1 から少なくとも一方の端 $u$ が $C$ の外にあります。その辺から $C$ の上の端点を除いたものは連結で、$C$ と交わらず、$u\in R_1$ を含むので、$R_1$ に含まれます。以上から $R_0$ は $G$ の点を含まず、補題 2.1 の 2 により、境界が $C$ の面です。

必要性. $C$ が面 $f$ の境界であるとします。補題 2.1 の 1 から $f=R_0$ としてよく、$R_0$ は $G$ の点を含みません。

1 を示す. $C$ が弦 $g=p_1p_2$ をもつと仮定します。$p_1,p_2$ は $C$ で隣り合わないので、$C-\{p_1,p_2\}$ は空でない 2 つの道 $Z_1^\circ,Z_2^\circ$ に分かれます。$G$ は 3-連結なので $G-\{p_1,p_2\}$ は連結で、$Z_1^\circ$ の頂点から $Z_2^\circ$ の頂点への道があります。そのうち最短のもの $Q$ を取ると、$Q$ の内点は $C$ の上になく、辺は $C$ の辺ではありません（$Z_1^\circ$ と $Z_2^\circ$ を直接結ぶ $C$ の辺はありません）。つまり $Q$ は $C$-道で、$g$ と頂点を共有せず、両端は $C-\{p_1,p_2\}$ の異なる成分にあります。補題 2.3 により、$g$ の内点と $Q$ の内点は $R_0,R_1$ の異なるほうにあり、どちらかが $R_0$ に入ります。これは $R_0$ が $G$ の点を含まないことに反します。

2 を示す. $u,u'$ を $C$ の外の相異なる頂点とします。$G$ は 3-連結なので、$u$ と $u'$ は 3 本の内素な道 $P_1,P_2,P_3$ で結ばれます（系 5.5［連結度とネットワークフロー］）。$\Theta=P_1\cup P_2\cup P_3$ の面は 3 つで、境界は $P_i\cup P_j$ です（補題 2.2）。$f$ は連結で $\Theta\subseteq G$ と交わらないので、$\Theta$ の 1 つの面 $\phi$ に含まれます。$\phi$ の境界が $P_1\cup P_2$ であるとすると、

$$C\subseteq\overline f\subseteq\overline\phi=\phi\cup P_1\cup P_2$$

です。$P_3$ の内点は $\Theta$ の点なので $\phi$ に属さず、$P_1\cup P_2$ にも属しません。よって $P_3$ の内点は $C$ の上になく、両端 $u,u'$ も $C$ の外なので、$P_3$ は $G-V(C)$ の中の道です。したがって $G-V(C)$ は連結です（$C$ の外の頂点が 1 つだけのときも連結です。1 つもないことは、1 と $G\ne C$ からありません）。

最後の主張は、条件 1・2 が描画を使わずに述べられていることから従います。

∎

例 7.2（3-連結でないと面の境界は描画で変わる）

2 頂点 $a,b$ を、辺 $ab$（$P_1$）と、長さ 2, 3, 4 の道 $P_2,P_3,P_4$ の、合わせて 4 本の内素な道で結んだグラフ $G$ を考えます。$\{a,b\}$ が分離集合なので、$G$ は 2-連結ですが 3-連結ではありません。$a$ を左、$b$ を右に置き、4 本の道を上から順に弧として描くと、面の境界は上下に隣り合う 2 本の道の和と、いちばん上といちばん下の道の和（外面）です。

• 上から $P_1,P_2,P_3,P_4$ の順に描くと、面の境界の長さは $P_1\cup P_2$ の $3$、$P_2\cup P_3$ の $5$、$P_3\cup P_4$ の $7$、$P_4\cup P_1$ の $5$ です。
• 上から $P_1,P_3,P_2,P_4$ の順に描くと、$P_1\cup P_3$ の $4$、$P_3\cup P_2$ の $5$、$P_2\cup P_4$ の $6$、$P_4\cup P_1$ の $5$ です。

長さ 3 の閉路 $P_1\cup P_2$ は、前者では面の境界で、後者ではそうではありません。定理 7.1 の条件で見ると、$G-V(P_1\cup P_2)$ は $P_3$ と $P_4$ の内点からなる非連結なグラフで、条件 2 が破れています。2 点 $a,b$ で切り離される部分を「裏返す」ことができるのが、描画が一意でない理由です。

注意 7.3（閉路マトロイドによる平面性の判定）

グラフの森を独立集合とするマトロイド（定義 8.1［グラフと行列式］、命題 8.4［グラフと行列式］）を使うと、平面性には別の特徴づけがあります。連結な平面グラフ $G$ とその幾何的双対 $G^*$ では、$G$ の全域木の補集合が $G^*$ の全域木に対応します（平面グラフの章）。Whitney は逆に、「全域木の補集合を基とするマトロイド（双対マトロイド）が、あるグラフの閉路マトロイドになる」ことが平面的であることと同値であることを示しました。禁止マイナーによる特徴づけは、マトロイドにも広がります。たとえば、あるグラフの閉路マトロイドになるマトロイドは、5 個の禁止マイナーで特徴づけられます（Tutte）。ここでは関連を述べるにとどめます。

注意 7.4（3-連結グラフの作り方と、平面性の判定アルゴリズム）

補題 4.1 を逆に読むと、3-連結グラフはどれも、$K_4$ から「頂点を 2 つに開く」操作をくり返して得られます。Tutte はこれを精密にして、3-連結グラフは車輪から、辺を足す操作と、次数 4 以上の頂点を次数 3 以上の 2 頂点に開く操作だけで作れることを示しました（車輪定理、1961 年）。

平面性は、頂点数に比例する時間で判定できます。最初の線形時間アルゴリズムは Hopcroft と Tarjan によるもの（1974 年）で、深さ優先探索で見つけた閉路に残りの部分を内側・外側へ埋め込んでいきます。平面的でないときに Kuratowski 部分グラフを出力するアルゴリズムも知られています。グラフの探索そのものはグラフアルゴリズムの記事にあります。

7.2. 外平面的グラフ

系 7.5（外平面的グラフの特徴づけ）✓

グラフ $G$ が外平面的であるためには、$K_4$ も $K_{2,3}$ も $G$ のマイナーでないことが必要十分である。

証明（系 7.5）

必要性. $G$ が外平面的で、$K_4$ か $K_{2,3}$ をマイナーに含むと仮定します。どちらも最大次数が 3 なので、補題 3.6 の 1 から、$G$ は $K_4$ か $K_{2,3}$ の細分 $K$ を部分グラフに含みます。$G$ の描画で、全頂点を閉包に含む面を $f_0$ とします。この描画から $K$ 以外を消すと、$f_0$ は連結で $K$ と交わらないので $K$ のある面 $f_0'$ に含まれ、$K$ の頂点はすべて $f_0'$ の閉包にあり、$K$ の点なので $f_0'$ の境界にあります。$K$ は 2-連結です（$K_4$ のどの 2 辺も共通の閉路に乗り、$K_{2,3}$ は 3 本の内素な道の和なので、細分のどの 2 頂点も共通の閉路に乗ります。定理 3.2［連結度とネットワークフロー］）。したがって $f_0'$ の境界は閉路 $Z$ で（命題 4.2［平面グラフ］）、$Z$ は $K$ の全頂点を通ります。$f_0'$ は $\mathbb{R}^2\setminus Z$ の連結成分の 1 つに等しく（補題 2.1）、$K$ の点を含みません。

$K$ が $K_{2,3}$ の細分のとき、$K$ は 2 つの分岐点を結ぶ、長さ 2 以上の 3 本の内素な道の和です。その閉路は 2 本の道の和で（補題 2.2 の証明）、残る 1 本の内点を通らないので、全頂点を通る閉路はありません。矛盾です。

$K$ が $K_4$ の細分のとき、頂点数を $n'$ とすると辺は $n'+2$ 本なので、$Z$ に乗らない辺はちょうど 2 本です。$Z$ の上で次数 3 の頂点（4 つの分岐点）は、それぞれ $Z$ に乗らない辺をちょうど 1 本もつので、2 本の辺は分岐点を 2 つずつ結ぶ $Z$ の弦 $b_1b_2$ と $b_3b_4$ です。$K$ の細分された辺は、この 2 本と、$Z$ を 4 つの分岐点で分けた 4 本の道です。$K_4$ ではどの 2 つの分岐点も細分された辺で結ばれるので、$b_1b_2$ と $b_3b_4$ 以外の 4 組 $b_1b_3,b_1b_4,b_2b_3,b_2b_4$ が $Z$ の上で隣り合い、$Z$ の上の巡回順は $b_1,b_3,b_2,b_4$ です。補題 2.3 により、2 本の弦の内点は $\mathbb{R}^2\setminus Z$ の異なる成分にあり、一方は $f_0'$ に入ります。矛盾です。

十分性. $K_4$ も $K_{2,3}$ も $G$ のマイナーでないとします。$G$ に新しい頂点 $v^*$ を足して全頂点と隣接させたグラフを $G^*$ とします。$G^*$ が $K_5$ の模型をもてば、$v^*$ を含む枝集合（なければ任意の 1 つ）を除いた 4 つの枝集合は $G$ の中の $K_4$ の模型です。$K_{3,3}$ の模型をもてば、同様に 1 つ除いて $K_{2,3}$ の模型が得られます。どちらも仮定に反するので、系 6.6 から $G^*$ は平面的で、系 6.7 から辺がすべて線分の描画をもちます。

その描画で $v^*$ を原点とします。$G$ の頂点 $u$ は、線分 $v^*u$ が辺なので、相異なる方向にあります（同じ方向に 2 頂点があれば、一方が他方への辺の上に乗ります）。各頂点 $u$ を、原点から $u$ の方向にある単位円周上の点 $\hat u$ に置き、$G$ の各辺 $uw$ を弦 $[\hat u,\hat w]$ で描きます。これが平面描画であることを示します。弦は端点以外で円周と交わらないので、他の頂点を通りません。端点を共有する 2 本の弦は、その端点でしか交わりません。端点を共有しない 2 本の弦 $[\hat u_1,\hat u_2]$ と $[\hat u_3,\hat u_4]$ は、$\hat u_3,\hat u_4$ が円周から $\hat u_1,\hat u_2$ を除いた同じ弧にあれば、直線 $\hat u_1\hat u_2$ の同じ側に厳密にあるので交わりません。

残るのは、$G$ の辺 $u_1u_2$ と $u_3u_4$ で、$\hat u_3$ と $\hat u_4$ が異なる弧にある場合です。これが起こらないことを示します。$u_1$ と $u_2$ の方向が正反対なら、$v^*$ が辺 $u_1u_2$ の上に乗ってしまうので、そうではなく、$v^*,u_1,u_2$ はつぶれていない三角形 $T$ をなします。$T$ の 3 辺は $G^*$ の辺です。仮定から、$u_3,u_4$ の一方、たとえば $u_3$ の方向は角 $u_1v^*u_2$ の内側に、$u_4$ の方向は外側にあります。線分 $v^*u_3$ から $v^*$ を除いた部分は、$v^*$ の近くで $T$ の内部にあり、$T$ の辺と交わらないので、$u_3$ は $T$ の内部にあります。$u_4$ は角の外側にあるので $T$ の外です。すると辺 $u_3u_4$ は $T$ の内部の点と外部の点を結ぶ線分で、$T$ の境界と交わります。これは、$G^*$ の描画で辺が端点以外で交わらないことに反します。

こうして、$G$ の頂点がすべて単位円周の上にあり、辺がすべて弦である平面描画が得られました。閉じた単位円板の外側は連結で、描画と交わらないので 1 つの面（外面）に含まれ、各頂点 $\hat u$ はその閉包にあります。よって全頂点が外面の閉包にあり、$G$ は外平面的です。

∎

証明から、外平面的グラフは「頂点を円周上に並べ、辺を交わらない弦として描けるグラフ」だと分かります。平面グラフの章の美術館定理は、この形の描画（多角形の三角形分割）についての定理でした。

8. 演習

演習 8.1標準

超立方体 $Q_4$（例 3.8）が $K_{3,3}$ をマイナーに含むことを、模型を具体的に与えて示せ。頂点は $0000$ から $1111$ までの 4 桁の 2 進列で表す。

解答

枝集合を次のように取ります。

$$\begin{aligned} &A_1=\{0000\},\quad A_2=\{0011,\ 0111\},\quad A_3=\{1101,\ 1100,\ 1110\},\\ &B_1=\{0001,\ 0101\},\quad B_2=\{0010,\ 0110\},\quad B_3=\{1000,\ 1001,\ 1011,\ 1010\}. \end{aligned}$$

合わせて 14 頂点で、互いに交わりません。各集合の中は、$0011$–$0111$、$1101$–$1100$–$1110$、$0001$–$0101$、$0010$–$0110$、$1000$–$1001$–$1011$–$1010$ と 1 桁ずつ違う頂点の列になっているので連結です。$A_i$ と $B_j$ の間の辺は次のとおりです。

	$B_1$	$B_2$	$B_3$
$A_1$	$0000$–$0001$	$0000$–$0010$	$0000$–$1000$
$A_2$	$0011$–$0001$	$0011$–$0010$	$0011$–$1011$
$A_3$	$1101$–$0101$	$1110$–$0110$	$1100$–$1000$

9 組すべてに辺があるので、$K_{3,3}$ は $Q_4$ のマイナーです。$\Delta(K_{3,3})=3$ なので、補題 3.6 の 1 から $Q_4$ は $TK_{3,3}$ も含みます。

演習 8.2易

$K_5$ から 1 辺を除いたグラフ $K_5^-$ は 3-連結で平面的である。3-連結であることを確かめ、凸な描画を座標で与えよ。

解答

除く辺を $ab$ とし、残りの 3 頂点を $c_1,c_2,c_3$ とします。$a,b$ はそれぞれ $c_1,c_2,c_3$ と隣接し、$c_1,c_2,c_3$ は互いに隣接します。

3-連結性. 頂点は 5 個なので、どの 2 頂点を除いても残りの 3 頂点が連結であることを言えば十分です。残る 3 頂点が $a,b$ の両方を含めば、3 つ目は $c_j$ で、$a,b$ の両方と隣接します。そうでなければ、残る 3 頂点のうち少なくとも 2 つは $c$ で、互いに隣接し、残りの 1 頂点とも隣接します。

描画. 辺は 9 本なので、面は $n-m+f=5-9+f=2$ から 6 個で、$2m=18=3\cdot6$ からどれも三角形です。$a$ と $b$ を両方とも三角形 $c_1c_2c_3$ の内部に置くことはできません（$a$ を内部に置いて 3 頂点と結ぶと 3 つの小三角形に分かれ、$b$ はそのどれかに入るので、その小三角形の頂点でない $c_j$ に辺を交えずには届きません）。そこで $a$ を外面の境界に置きます。

$$a=(0,0),\quad c_1=(12,0),\quad c_2=(6,12),\quad c_3=(6,3),\quad b=(7,5).$$

外側の三角形は $a\,c_1\,c_2$ です。$c_3=(6,3)$ は、$y>0$、$2x+y=15<24$（直線 $c_1c_2$ の $a$ の側）、$y<2x$（直線 $ac_2$ の $c_1$ の側）を満たすので内部にあり、3 頂点と結ぶと三角形 $ac_1c_3$、$c_1c_2c_3$、$c_2ac_3$ に分かれます。$b=(7,5)$ が三角形 $c_1c_2c_3$ の内部にあることは、3 辺に対する符号で確かめられます。

$$\begin{aligned} [c_1,c_2,b]&=\det\bigl((-6,12),(-5,5)\bigr)=-30+60=30>0,\\ [c_2,c_3,b]&=\det\bigl((0,-9),(1,-7)\bigr)=0+9=9>0,\\ [c_3,c_1,b]&=\det\bigl((6,-3),(1,2)\bigr)=12+3=15>0. \end{aligned}$$

$b$ を $c_1,c_2,c_3$ と線分で結ぶと、内面は $ac_1c_3$、$c_2ac_3$、$c_1c_2b$、$c_2c_3b$、$c_3c_1b$ の 5 つの三角形、外面の境界は三角形 $ac_1c_2$ で、合わせて 6 面です。つぶれていない三角形の 3 頂点は狭義凸の位置にあるので、これは凸な描画です。

演習 8.3標準

頂点数 $n\ge2$ の外平面的グラフの辺の数は $2n-3$ 以下であることを示せ。系 7.5 の証明で得た「頂点を円周上に置き、辺を交わらない弦で描く」描画を使ってよい。

解答

$n$ についての帰納法で、凸 $n$ 角形の頂点を結ぶ、端点以外で交わらない線分（辺と対角線）は高々 $2n-3$ 本であることを示します。円周上の $n$ 点は狭義凸の位置にあるので、これで十分です。

$n=2$ なら線分は 1 本、$n=3$ なら高々 3 本で、主張は正しい。$n\ge4$ とします。対角線が 1 本もなければ、線分は多角形の辺の $n$ 本以下で、$n\le2n-3$ です。対角線 $[v_i,v_j]$ があれば、それは頂点を $v_i,\dots,v_j$ の $n_1$ 個と $v_j,\dots,v_i$ の $n_2$ 個に分けます（$n_1+n_2=n+2$、$n_1,n_2\ge3$）。他の線分は $[v_i,v_j]$ と交わらないので、両端がどちらか一方の組に入ります（両端が 2 つの組に分かれる線分は、端点が $v_i,v_j$ と交互に並ぶ弦で、$[v_i,v_j]$ と交わります）。それぞれの組は凸多角形の頂点なので、帰納法の仮定から線分は $2n_1-3$ 本以下と $2n_2-3$ 本以下です。$[v_i,v_j]$ は両方に数えられているので、全体では

$$(2n_1-3)+(2n_2-3)-1=2(n+2)-7=2n-3$$

本以下です。

$K_4$ は $n=4$ で辺が $6>5$、$K_{2,3}$ は $n=5$ で辺が $6\le7$ です。前者はこの評価だけで外平面的でないと分かりますが、後者は分かりません。$K_{2,3}$ が外平面的でないことは、系 7.5 の証明のとおり、全頂点を通る閉路がないことから従います。

演習 8.4標準

立方体のグラフ $Q_3$ は 3-連結で平面的である。定理 7.1 を使って、$Q_3$ の長さ 4 の閉路 6 個がすべて面の境界であり、長さ 6 の閉路はどれも面の境界でないことを示せ。

解答

$Q_3$ の頂点は $\{0,1\}^3$ の 8 個です。まず 3-連結性を確かめます。$Q_3$ は、$x_3=0$ の 4 頂点の閉路、$x_3=1$ の 4 頂点の閉路と、対応する頂点どうしを結ぶ 4 本の辺からなります。2 頂点を除くとします。同じ閉路から 2 つ除いた場合、もう一方の閉路は無傷で連結で、残った頂点はどれも無傷の閉路に相手をもちます。1 つずつ除いた場合、どちらの閉路も 3 頂点の道になって連結で、4 本の対応の辺のうち壊れるのは高々 2 本なので、2 つの道は結ばれています。どちらの場合も連結です。

長さ 4 の閉路は、1 つの座標を固定した 4 頂点が作るもので、座標 3 通りと値 2 通りで 6 個です。たとえば $C=\{x_3=0\}$ の 4 頂点の閉路を取ると、$C$ の対角にある 2 頂点は 2 座標が異なるので隣接せず、弦はありません。$Q_3-V(C)$ は $\{x_3=1\}$ の 4 頂点の閉路で連結です。定理 7.1 から $C$ は面の境界です。

面の個数は $n-m+f=8-12+f=2$ から $6$ なので、面の境界はこの 6 個で尽きます。したがって長さ 6 の閉路は面の境界ではありません。定理の条件で直接確かめることもできます。長さ 6 の閉路 $C'$ は 6 頂点を通り、残りは 2 頂点です。$Q_3$ は 3-正則で、$C'$ の各頂点は $C'$ の外か弦に 1 本の辺を出します。$C'$ に弦がなければ、6 本の辺がすべて残りの 2 頂点に入りますが、2 頂点が受けられるのは次数の和 $6$ から互いを結ぶ辺の分を引いた本数までで、6 本を受けるには 2 頂点が隣接していない必要があります。このとき $Q_3-V(C')$ は辺のない 2 頂点で非連結です。弦があれば条件 1 が破れます。どちらにしても $C'$ は面の境界ではありません。

参考文献

• R. Diestel, Graph Theory, 5th ed., Graduate Texts in Mathematics 173, Springer, 2017 — 3.2 節（3-連結グラフと縮約できる辺）、4.2・4.3 節（面の境界と描画の一意性）、4.4 節（Kuratowski の定理）、第 12 章（グラフマイナー定理）。
• C. Thomassen, “Kuratowski’s theorem”, Journal of Graph Theory 5 (1981), 225–241 — 3-連結グラフの凸な描画を帰納法で作る証明。
• K. Kuratowski, “Sur le problème des courbes gauches en topologie”, Fundamenta Mathematicae 15 (1930), 271–283.
• K. Wagner, “Über eine Eigenschaft der ebenen Komplexe”, Mathematische Annalen 114 (1937), 570–590.
• N. Robertson and P. D. Seymour, “Graph minors. XX. Wagner’s conjecture”, Journal of Combinatorial Theory, Series B 92 (2004), 325–357.
• J. Hopcroft and R. Tarjan, “Efficient planarity testing”, Journal of the ACM 21 (1974), 549–568.