外平面グラフ

（$G\ast v$ が平面グラフなら $G$ は外平面グラフ。）$G\ast v$ の描画から $v$ とそれに接続する辺を除くと $G$ の描画が得られ、点 $v$ は $G$ のある面 $f$ に入る。$G$ の頂点 $x$ について、辺 $vx$ から点 $x$ を除いた集合は連結で $G$ と交わらず $v$ を含むので $f$ に含まれる。よって $x$ は $f$ の閉包に入り、$f$ に属さないので $f$ の境界の点である。(F5) により $f$ を外側の面に移すと、$G$ の外平面描画が得られる。
（$G$ が外平面グラフなら $G\ast v$ は平面グラフ。）要点：外側の面に点 $v$ を置き、$G$ の頂点 $x_1,\dots,x_n$ と 1 本ずつ結んでいく。そのたびに、まだ結んでいない頂点が「$v$ を境界にもつ面」の境界にのっていることを保つ。

lem-otp-apex と Kuratowskiの定理 の定理「Kuratowski–Wagner の定理」の 1 ⇔ 2 により、$G$ が外平面グラフであることは、$G\ast v$ が $K_5$ も $K_{3,3}$ もマイナーとして含まないことと同値である。そこで次の 2 つを示せばよい。
(a) $G$ が $K_4$ をマイナーとして含めば $G\ast v$ は $K_5$ を、$G$ が $K_{2,3}$ を含めば $G\ast v$ は $K_{3,3}$ を含む。$G$ での分岐集合（Kuratowskiの定理 の定義「マイナー」）に $\{v\}$ を 1 つ加えればよい。$v$ は $G$ のすべての頂点と隣接するので、$\{v\}$ はほかのすべての分岐集合と辺で結ばれる。$K_4$ の 4 つに加えれば $K_5$ の分岐集合になる。$K_{2,3}$ の分岐集合を $A_1,A_2$（2 個の側）と $B_1,B_2,B_3$ とし、$\{v\}$ を $A_1,A_2$ の側に加えれば、$\{v\}$ は $B_1,B_2,B_3$ と結ばれるので $K_{3,3}$ の分岐集合になる。
(b) $G\ast v$ が $X\in\{K_5,K_{3,3}\}$ をマイナーとして含めば、$G$ は $K_4$ か $K_{2,3}$ を含む。分岐集合 $V_x$（$x\in V(X)$）をとる。$v$ がどの $V_x$ にも属さなければ、分岐集合はすべて $G$ の中にあり、$G$ は $X$ を含む。$K_5$ は $K_4$ を、$K_{3,3}$ は $K_{2,3}$ を部分グラフとして含むので、$G$ はそれらもマイナーとして含む（マイナーのマイナーはマイナー）。$v\in V_{x_0}$ なら、$V_{x_0}$ を除いた残りの分岐集合は $v$ を含まないので $G$ の連結な部分グラフを誘導し、それらの間の辺は $v$ に接続しないので $G$ の辺である。よって $G$ は $X-x_0$ をマイナーとして含む。$K_5-x_0=K_4$、$K_{3,3}-x_0=K_{2,3}$ である。$\square$

$M$ が外平面グラフ $G$ のマイナーで、$M$ が $K_4$ か $K_{2,3}$ をマイナーとして含めば、$G$ も含み、thm-otp-minor に反する。部分グラフはマイナーである（分岐集合を 1 点ずつにとる）。$\square$

$G$ を $n$ 頂点・$m$ 辺の単純な外平面グラフとする。lem-otp-apex により $G\ast v$ は $n+1\ge3$ 頂点・$m+n$ 辺の単純な平面グラフなので、平面グラフ の系「単純平面グラフの辺数の上界」により $m+n\le3(n+1)-6$、すなわち $m\le2n-3$ である。$\square$

1. (F3) により $f$ の境界は閉路 $C$ で、外平面描画なのですべての頂点は $C$ の上にある。
2. (F2) により $f$ は $C$ の面でもあり、有界でないので $\mathbb{R}^2\setminus C$ の有界でない領域に等しい。弦 $e$ の内部は $C$ とも $f$ とも交わらない（$e$ は $G$ の辺で、$f$ は $G$ と交わらない）ので、有界な領域に含まれる。
3. $i< k< j< l$ とする。$C$ から $x_i,x_j$ を除くと 2 本の道に分かれ、$x_k$ は一方、$x_l$ は他方の内部にある。それぞれに $x_i,x_j$ を付けた折れ線を $P_1\ni x_k$、$P_3\ni x_l$、弦 $x_ix_j$ を $P_2$ とすると、3 本は端点 $x_i,x_j$ だけを共有する。$P_1\cup P_3=C$ で、(2) により $P_2$ の内部も弦 $x_kx_l$ の内部も有界な領域にある。(F4) により 2 本の弦の内部は交わり、描画であることに反する。$\square$

prop-otp-hamilton の記号を使う。弦がなければ $G=C$ で、すべての頂点の次数は $2$ である。
弦 $x_ix_j$（$i< j$）について、$C$ の上で $x_i$ と $x_j$ の間にある頂点の集合の 2 つ $A=\{x_{i+1},\dots,x_{j-1}\}$ と $A'$（残りの側）を、この弦の 側 という。弦なので $x_i,x_j$ は $C$ の上で隣り合わず（単純グラフなので、隣り合えばその辺は $C$ の辺である）、$A,A'$ は空でない。弦とその側 $A$ のすべての組について、$A$ が次数 $2$ の頂点を含むことを $\lvert A\rvert$ についての帰納法で示す（$A'$ の側は、番号を巡回的にずらして $A$ の形にすればよい）。
$A$ の頂点に接続する弦がなければ、$A$ の頂点の辺は $C$ の 2 本だけで、次数は $2$ である。$A$ の頂点 $x_k$ に接続する弦 $x_kx_l$ があるとする。prop-otp-hamilton の 3 により、$x_l$ は $A\cup\{x_i,x_j\}$ に属する。このとき弦 $x_kx_l$ の側のうち $A$ に含まれる方 $A_1$（$x_k$ と $x_l$ の間で、$x_i,x_j$ を通らない側）は、$x_k$ を含まないので $\lvert A_1\rvert<\lvert A\rvert$ である。帰納法の仮定により $A_1$ は次数 $2$ の頂点を含む。
$A$ と $A'$ は交わらないので、次数 $2$ の頂点が 2 つ得られる。$\square$

$G$ を単純な外平面グラフとする。$G$ が連結でなければ連結成分（cor-otp-minor-closed により外平面）を考えればよく、頂点が $2$ 個以下なら明らかなので、$G$ は連結で $3$ 頂点以上とする。$G$ が 2-連結なら lem-otp-two による。
そうでなければ切断点がある。切断点 $c$ と $G-c$ の連結成分 $K$ の組で、$\lvert K\rvert$ が最小のものをとり、$H:=G[K\cup\{c\}]$ とおく。$K$ の頂点の $G$ での隣接頂点はすべて $K\cup\{c\}$ にあるので、$K$ の頂点の次数は $G$ と $H$ で等しい。$\lvert K\rvert=1$ なら、その頂点の次数は $1$ 以下である。
$\lvert K\rvert\ge2$ とし、$H$ が 2-連結であることを示す。$H$ は連結で $3$ 頂点以上である。$H-c=G[K]$ は連結なので $c$ は $H$ の切断点でない。$w\in K$ が $H$ の切断点だとすると、$H-w$ の連結成分で $c$ を含まないもの $K'$ がある。$K'$ の頂点は $c$ と隣接せず、隣接頂点は $K'\cup\{w\}$ にあるので、$K'$ は $G-w$ の連結成分で、$w$ は $G$ の切断点である（$G-w$ には $c$ を含む別の成分がある）。$K'\subset K\setminus\{w\}$ なので $\lvert K'\rvert<\lvert K\rvert$ となり、最小性に反する。
よって $H$ は 2-連結な外平面グラフ（cor-otp-minor-closed）で、lem-otp-two により次数 $2$ の頂点が 2 つある。その一方は $c$ でなく $K$ に属し、$G$ での次数も $2$ である。$\square$

頂点の個数についての帰納法による。thm-otp-degree により次数 $2$ 以下の頂点 $u$ がある。$G-u$ は外平面グラフ（cor-otp-minor-closed）なので帰納法の仮定により 3 色で塗り分けられ、$u$ の隣接頂点は 2 個以下なので、$u$ に残りの色を塗ればよい。$\square$