Kuratowskiの定理

1：分岐集合を $V_x$（$x\in V(X)$）とする。$X$ の各辺 $xy$ について $V_x$ と $V_y$ を結ぶ $G$ の辺 $e_{xy}$ を 1 本ずつ選ぶ。$e_{xy}$ の $V_x$ 側の端点の集合を $S_x$ とすると $1\le\lvert S_x\rvert\le3$ である（$X$ に孤立点があればその $V_x$ の 1 点を $S_x$ とする）。$G[V_x]$ は連結なので、$S_x$ を含む $G[V_x]$ の部分木で頂点数が最小のもの $T_x$ がある。最小性から $T_x$ の葉はすべて $S_x$ に属するので、$T_x$ の葉は高々 $3$ 個である。葉が $3$ 個なら、葉は $S_x$ の 3 頂点で、次数 $3$ の頂点がちょうど 1 つある（木では $\sum_v(\deg v-2)=-2$ である）のでそれを $b_x$ とする。葉が $2$ 個以下なら $T_x$ は道で、両端は $S_x$ に属する。このときは、$T_x$ の内部にある $S_x$ の頂点があればそれを、なければ 2 本の $e_{xy}$ の端点になっている端点があればそれを、どちらもなければ一方の端点を $b_x$ とする。どの場合も、$T_x$ は $b_x$ から $S_x$ の各頂点への道で $b_x$ 以外を共有しないものの和であり、$b_x$ 以外の $S_x$ の頂点はちょうど 1 本の $e_{xy}$ の端点である（$x$ の次数は $3$ 以下だから）。各辺 $xy$ について、$T_x$ の中の $b_x$ から $e_{xy}$ の端点への道、辺 $e_{xy}$、$T_y$ の中の $e_{xy}$ の端点から $b_y$ への道をつなぐと $b_x$ と $b_y$ を結ぶ道 $P_{xy}$ になる。分岐集合は互いに交わらず、$T_x$ の中の道は $b_x$ 以外を共有しないので、$P_{xy}$ たちは端点以外を共有しない。よって $\{b_x\}$ と $P_{xy}$ たちは $X$ の細分である。

2：位相的マイナーならマイナーなので、逆を示す。$K_{3,3}$ は最大次数 $3$ なので 1 により位相的マイナーになる。$G$ が $K_5$ をマイナーとして含むとする。$K_5$ のマイナーの分岐集合 $V_1,\dots,V_5$ と、各 $V_i$ の中の全域木と、$V_i$ と $V_j$ を結ぶ辺 1 本ずつからなる部分グラフ $M$ を、辺の数が最小になるように選ぶ。$V_i$ の全域木に $V_i$ から出る 4 本の辺を加えたものは木 $T_i$ で、最小性から $T_i$ の葉はちょうどこの 4 本の辺の外側の端点である（$V_i$ の中の葉は、$\lvert V_i\rvert\ge2$ なら除いても分岐集合の条件が保たれる）。葉が 4 個の木では、$\sum_v(\deg v-2)=-2$ から、次数 $3$ 以上の頂点は次数 $4$ の 1 個か、次数 $3$ の 2 個である。すべての $i$ で前者なら、その次数 $4$ の頂点 $c_i\in V_i$ を分岐点として、$T_i$ の中の $c_i$ から各葉への道をつなげば $M$ は $K_5$ の細分である。ある $i$ で後者なら、次数 $3$ の頂点 $a,b$（葉でないので $V_i$ に属する）を結ぶ $T_i$ の道の辺を 1 本除いて $V_i$ を 2 つに分け、$a$ 側を $V_a$、$b$ 側を $V_b$ とする。$V_a$ からは 2 つの $V_j$、たとえば $V_{j_1},V_{j_2}$ へ辺が出て、$V_b$ からは残りの $V_{j_3},V_{j_4}$ へ辺が出て、$V_a$ と $V_b$ は辺で結ばれる。$V_{j}$ どうしはすべて辺で結ばれているので、$\{V_a,V_{j_3},V_{j_4}\}$ と $\{V_b,V_{j_1},V_{j_2}\}$ は $K_{3,3}$ のマイナーの分岐集合である。1 によりこれは $K_{3,3}$ の位相的マイナーを与える。$\square$

3-連結で頂点数 $4$ のグラフは $K_4$ なので $\lvert G\rvert\ge5$ であり、$\lvert G/e\rvert\ge4$ である。どの辺 $xy$ についても $G/xy$ が 3-連結でないとする。すると $G/xy$ を分離する高々 $2$ 個の頂点の集合 $S$ がある。$v_{xy}\notin S$ なら、$S$ は $G$ も分離する（$G-S$ が連結なら、そこで辺 $xy$ を縮約した $G/xy-S$ も連結である）ので矛盾する。$S=\{v_{xy}\}$ なら $\{x,y\}$ が $G$ を分離して矛盾する。よって $S=\{v_{xy},z\}$（$z\ne x,y$）で、$G/xy-S$ の異なる成分の頂点は $G$ で $T:=\{x,y,z\}$ により分離される。$T$ の真部分集合は $G$ を分離しないので、$T$ の各頂点は $G-T$ のどの成分にも隣接頂点をもつ（$t\in T$ が成分 $C$ に隣接頂点をもたなければ、$T\setminus\{t\}$ が $C$ を他の成分から分離する）。

辺 $xy$、頂点 $z$、$G-\{x,y,z\}$ の成分 $C$ の組を、$\lvert C\rvert$ が最小になるように選び、$z$ の $C$ の中の隣接頂点 $v$ をとる。上と同じ理由で、ある頂点 $w$ について $\{z,v,w\}$ は $G$ を分離し、$z,v,w$ はどれも $G-\{z,v,w\}$ のどの成分にも隣接頂点をもつ。$x$ と $y$ は隣接するので、$x,y$ を含まない $G-\{z,v,w\}$ の成分 $D$ がある（$x,y$ のうち除かれていないものは同じ成分に入り、成分は 2 つ以上ある）。$v$ は $D$ に隣接頂点をもち、$v\in C$ の隣接頂点は $C\cup T$ に属し、$D$ は $T=\{x,y,z\}$ と交わらないので、その隣接頂点は $C$ に属する。よって $D\cap C\neq\emptyset$ である。$D$ は $G-T$ の連結な部分なので $D\subset C$ であり、$v\in C\setminus D$ だから $\lvert D\rvert<\lvert C\rvert$ である。辺 $zv$、頂点 $w$、成分 $D$ の組はこの最小性に反する。$\square$

1：$A$ の頂点と $B$ の頂点を結ぶ $H$ の道は、$S$ の頂点を内部に含むか $F$ の辺を含む。$A$ と $B$ を結ぶ道の族で、どの道の内部の頂点もほかの道にのらないものを考えると、各道は別々の出口を通る（$F$ の辺 $a'b'$ を 2 本の道が含めば、$a',b'$ は両方の道の端点でなければならず、2 本とも辺 $a'b'$ そのものになる）。よって、そのような族の道の本数は $m$ 以下である。分岐点 $a\in A$、$b\in B$ があるとき、$X$ の中で $a$ と $b$ を結び内部を共有しない道は、$K_5$ では 4 本（辺 $ab$ と残りの 3 頂点 $c$ を通る $acb$）、$K_{3,3}$ では 3 本（$a,b$ が同じ側なら反対側の 3 頂点を通る道、反対側なら辺 $ab$ と $a\,q\,p\,b$ の形の 2 本）ある。これらは $K$ の中で内部を共有しない $a$-$b$ 道を与える。$K_{3,3}$ の部を $P,Q$ とし、分岐点 $a_1,a_2\in A$、$b_1,b_2\in B$ があるとき、$\{a_1,a_2\}$ と $\{b_1,b_2\}$ を結ぶ 4 本の道で、内部を共有せず内部に $a_1,a_2,b_1,b_2$ を含まないものがある：$a_1,a_2\in P$、$b_1,b_2\in Q$ なら 4 本の辺 $a_ib_j$、$a_1,a_2\in P$、$b_1\in P$、$b_2\in Q$ なら辺 $a_1b_2,a_2b_2$ と $b_2$ 以外の $Q$ の 2 頂点 $q,q'$ を通る $a_1qb_1$、$a_2q'b_1$、$a_1\in P$、$a_2\in Q$、$b_1\in P$、$b_2\in Q$ なら辺 $a_1b_2,a_2b_1$ と残りの $q\in Q$、$p\in P$ を通る $a_1qb_1$、$a_2pb_2$ である（他の場合は $P,Q$ や $a,b$ の役割を入れ替えたもの）。

2：分岐点でない $K$ の頂点は次数 $2$ なので、$B$ に属する $K$ の頂点 $b$ から $K$ を両方向にたどると、$B$ の中を進んでやがて $B$ の外に出る（$b$ を含む $X$ の辺の道の両端は分岐点で、$B$ の外にある）。こうして $b$ を内部に含む $B$ 区間がただ 1 つ定まる。$B$ 区間 $Q$ の両端を $u,w$ とし、$Q$ を含む $X$ の辺の道を $R$ とする。$uw\in K$ とすると、$u,w$ がともに分岐点なら $R=Q$ と辺 $uw$ が同じ 2 つの分岐点を結ぶ $X$ の 2 本の辺に対応して $X$ の単純性に反し、そうでなければ $u,w$ の一方は $R$ の内部の次数 $2$ の頂点で、その 2 本の辺はどちらも $R$ の辺なので $uw\in R$ となり、$R$ が閉路を含んで矛盾する。同じ理由で異なる $B$ 区間の両端の組は異なる。各 $R$ の中の $B$ 区間を辺に置き換えても、$R$ は同じ分岐点を結ぶ道のままで、異なる $R$ は端点以外を共有しないので、$X$ の細分が得られる。最後の主張：$B$ 区間の端点 $u$ に隣接する区間内の頂点は $B$ に属し、$G$ には $A$ と $B$ を結ぶ辺がないので、$u\in S$ であるか、その辺が $F$ の辺である。$\square$

$\lvert G\rvert$ についての帰納法で示す。$\lvert G\rvert=4$ なら細分を含みえないので $G=K_4$ で、3-連結である。$\lvert G\rvert\ge5$ とし、3-連結でないとする。分離集合の大きさが最小の分離 $(V_1,V_2)$ をとり、$S,A,B$ を上のとおりとすると $k:=\lvert S\rvert\le2$ である。最小性から、$S$ の各頂点は $G-S$ のどの成分にも隣接頂点をもつ。以下、lem-kur-exits を使う。そこで $K$ の分岐点が $B$ にないとき「$K$ は $V_1$ の側にある」という（$A$ にないときは $V_2$ の側。$X$ の分岐点は 5 個以上で $\lvert S\rvert\le2$ なので、1 の条件が成り立たなければどちらかの側にある）。

段 1（$S\neq\emptyset$）．$k=0$ なら、$a\in A$、$b\in B$ として $G+ab$ は細分 $K$ を含み、$K\not\subset G$ なので $K$ は辺 $ab$ を含む。出口は 1 個なので 1 により $K$ はどちらかの側、たとえば $V_1$ の側にある。$K$ は $b\in B$ を含むので $B$ 区間があるが、その両端はどちらも出口を通るので 2 個の出口が要り、矛盾する。

段 2（$k=1$ はない）．$S=\{v\}$ とし、$v$ の隣接頂点 $v_1\in A$、$v_2\in B$ をとる。$G+v_1v_2$ の細分 $K$ は辺 $v_1v_2$ を含み、出口は 2 個なので $K$ はどちらかの側にあり、対称性から $V_1$ の側としてよい。$B$ 区間は両端で別々の出口を通るので、$v$ と辺 $v_1v_2$ を通る 1 本 $v\cdots v_2v_1$ だけである。2 によりそれを辺 $vv_1$ に置き換えると、$G[V_1]\subset G$ の中の細分が得られ、矛盾する。

段 3（$S=\{x,y\}$ なら $xy\in G$）．$xy\notin G$ とする。$G+xy$ の細分 $K$ は辺 $xy$ を含む。$(V_1,V_2)$ は $G+xy$ の分離でもあるので、$G+xy$ を $G$ の代わりにして lem-kur-exits を使う（$F=\emptyset$）。出口は $x,y$ の 2 個なので、対称性から $K$ は $V_1$ の側にあるとしてよい。$B$ 区間があればその両端は $x,y$ で、2 により辺 $xy$ は $K$ に属さないことになり矛盾する。よって $K$ は $B$ と交わらない。$x,y$ は $B$ を含む $G-S$ の成分 $D$ に隣接頂点をもつので、内部が $D$ に含まれる $x$-$y$ 道 $Q$ がある。$K$ の辺 $xy$ を $Q$ に置き換えると $G$ の中の細分になり、矛盾する。

段 4（$G_i:=G[V_i]$ は極大）．$G_1$ の隣接しない 2 頂点 $u,w$ をとる。$G+uw$ の細分 $K$ は $uw$ を含む。段 3 と同じく $G+uw$ に lem-kur-exits を使うと、出口は $x,y$ の 2 個なので、$K$ はどちらかの側にある。$V_1$ の側なら、$B$ 区間の両端は $x,y$ なので 2 によりそれを辺 $xy\in G_1$ に置き換えて $G_1+uw$ の中の細分を得る。$V_2$ の側なら、同様に $A$ 区間を $xy$ に置き換えて $G_2\subset G$ の中の細分を得るが（$uw$ は $A$ 区間に含まれて消える）、これは矛盾である。よって $G_1+uw$ は細分を含み、$G_1$ は極大である。$G_2$ も同様である。

段 5（矛盾）．$\lvert G_i\rvert<\lvert G\rvert$ なので、帰納法の仮定により $G_i$ は 3-連結であるか、$\lvert G_i\rvert=3$ で三角形である。どちらの場合も $G_i$ は細分を含まないので lem-kur-minor-top によりマイナーも含まず、lem-kur-three-connected により（三角形なら明らかに）平面グラフである。$G_i$ の描画で、辺 $xy$ を境界にもつ面 $f_i$ を選ぶ（(F2)）。$G_i$ は 2-連結なので (F3) により $f_i$ の境界は $xy$ を含む閉路で、$x,y$ と異なる頂点 $z_i$ をもつ（$z_1\in A$、$z_2\in B$）。$G+z_1z_2$ の細分 $K$ を考える。出口は $x,y,z_1z_2$ の 3 個である。

$K$ が $V_1$ の側にあるとき、$K$ は $z_1z_2$ を含み（そうでなければ $K\subset G$）、$z_1z_2$ を通る $B$ 区間の両端は $z_1$ と $x,y$ の一方 $t$ である。ほかの $B$ 区間の両端は $x,y$ である。2 により $B$ 区間を辺 $z_1t$ と $xy$ に置き換えると、$G_1+z_1t$ の中の細分が得られる。ところが $z_1,t$ は $f_1$ の境界の閉路の頂点なので、(F4) により $G_1+z_1t$ は平面グラフであり、prop-kur-subgraph-subdivision の 3 に反する。$V_2$ の側にあるときも同様である。

$K$ がどちらの側にもないとき、1 により $X=K_{3,3}$ で、一方の側、たとえば $B$ にはちょうど 1 個の分岐点 $v$ がある。$v$ から出る $K$ の 3 本の道は $V_1$ の分岐点へ向かい、$v$ 以外を共有しないので、別々の出口 $x,y,z_1z_2$ を 1 つずつ通る。$K$ の $B$ の部分は、この 3 本の $v$ から出口までの部分と、両端が $x,y$ の $B$ 区間（2 と同じ議論が使える）だけである。前者を辺 $vx,vy,vz_1$ に、後者を辺 $xy$ に置き換えると、$G_1$ に頂点 $v$ と辺 $vx,vy,vz_1$ を加えたグラフの中の $K_{3,3}$ の細分が得られる。(F4) によりこのグラフは平面グラフ（$v$ を $f_1$ の中に置く）であり、矛盾する。以上より $G$ は 3-連結である。$\square$