5-4 平面性判定の構造

縮約は $u,v$ を $w$ と同一視した以外には頂点を変えません。二本の接続辺が同じpreimage頂点へ接続していれば、その頂点を $w$ の代わりに置けばよいです。
異なるpreimage頂点へ接続していれば、その二頂点の間には縮約した辺 $uv=e$ があります。従って $x$ 側から一方へ入り、$e$ を一度通り、他方から $y$ 側へ出られます。元の $P$ はsimpleで $w$ を一度しか通らないため、追加した $u,v$ は他の持上げ部分に現れず、得られるwalkはsimple pathです。□

$G/e$ に含まれるsubdivisionを $S$ とします。縮約頂点 $w$ が $S$ に属さなければ、$S$ はそのまま $G$ の部分graphです。
$w$ が $S$ のdivision vertexなら、$S$ における次数は2です。$w$ を通るただ一つのbranch-to-branch pathへ前補題を適用すれば、そのpathだけを $G$ へ持ち上げられます。他のpathは $w$ を使わないので内部頂点の非共有性は保たれます。
$w$ がbranch vertexである場合を考えます。$S$ が $K_{3,3}$ subdivisionなら、$w$ から三本のbranch pathが出ます。それらの最初の辺を、$G$ で $u$ に接続する群と $v$ に接続する群へ分けます。
全てが同じ側なら、その側をbranch vertexにすればそのまま持ち上がります。分布が1本対2本なら、2本側の頂点をbranch vertexとし、1本側のpathの先頭へ辺 $uv$ を加えます。辺 $uv$ はその一本だけに使われ、反対側の頂点はそのpathの内部頂点になります。他のbranch pathと内部で交わらないため、$K_{3,3}$ subdivisionが得られます。
$S$ が $K_5$ subdivisionなら、$w$ から四本のbranch pathが出ます。分布が0本対4本または1本対3本なら、同じ議論で3本以上を受け持つ側をbranch vertexにし、必要なら残る一本へ $uv$ を加えて $K_5$ subdivisionを持ち上げられます。
残るのは2本対2本です。$w$ 以外の四branch vertexを $a,b,c,d$ とし、$u$ 側へ向かう二本のpathの終点を $a,b$、$v$ 側を $c,d$ と名付けます。元の $K_5$ subdivisionには、$a,b,c,d$ の各二頂点を結ぶbranch pathが全てあります。
ここで六頂点を
$$ X=\{u,c,d\},\qquad Y=\{v,a,b\} $$
に分けます。$X$ と $Y$ の九組を結ぶpathは次の通りです。
$$ \begin{array}{c|ccc} & v&a&b\\ \hline u&uv&u\leadsto a&u\leadsto b\\ c&v\leadsto c&c\leadsto a&c\leadsto b\\ d&v\leadsto d&d\leadsto a&d\leadsto b \end{array} $$
表の $u\leadsto a,u\leadsto b,v\leadsto c,v\leadsto d$ は $w$ に接続していた四branch pathを持ち上げたものです。残る四本は $K_5$ subdivision内の $a,c$、$a,d$、$b,c$、$b,d$ 間branch pathです。
これら九本の内部は互いに交わりません。元の $K_5$ の異なる辺に対応するpathは内部頂点を共有せず、$u,v$ は新しいbranch vertexとしてのみ現れ、辺 $uv$ は一つのpathとして使われるからです。従って表は $K_{3,3}$ subdivisionを与えます。
全ての場合に $G$ が二つの障害の少なくとも一つを含みます。□

対偶は直前の補題そのものです。□

二群が連続なら、$w$ の十分小さい円板 $D$ を取り、円周上で $U$ 型が入る区間と $V$ 型が入る区間を分けます。$D$ の内部に $u,v$ を置き、各区間のedge-endを交差しない扇形のarcで対応頂点へ結びます。二つの扇形の間に辺 $uv$ を引けるので、$D$ の外を変えずにplane描画が得られます。
逆に $D$ の外を変えない分裂描画があるとします。$D$ 内の辺 $uv$ と、$u,v$ のごく小さい近傍を合わせた細い閉円板 $N$ を取ります。$D$ の境界から $u$ へ入る $U$ 型arcの端は $\partial N$ の $u$ 側区間に、$V$ 型arcの端は $v$ 側区間にあります。互いに交差しないarcの巡回順は境界間で保存されるため、$\partial D$ 上でも全 $U$ 型端が一つの区間、全 $V$ 型端が残る区間に並びます。従って二群は連続です。□

平面へ一点 $\infty$ を加えた球面を考えると、plane embeddingは球面上のembeddingとみなせます。$F$ の内部の一点 $p$ を選び、球面の回転に相当するhomeomorphismで $p$ を $\infty$ へ移します。その後 $\infty$ を除いて平面へ戻せば、元の $F$ が非有界な外面になります。homeomorphismは交差の有無と接続関係を変えません。□

各graphをplane embeddingし、$x$ に接する面を外面へ移します。一方を左半平面の小円板、他方を右半平面の小円板へ縮小し、二つの $x$ だけを原点で同一視します。各辺は自分の開半平面内にあり、異なる側の辺は交差しません。従って和graphのplane embeddingが得られます。□

各 $G_i$ のplane embeddingで辺 $xy$ に接する面を外面へ移します。辺 $xy$ を水平線分として、一方のgraphをその上側、他方を下側に変形して置きます。共通辺と端点を同一視すれば、上側と下側の内部は交わりません。従って和はplanarです。□

$G$ が非連結なら、各連結成分は $G$ より頂点数が少なく、障害を含まないので、最小性によりplanarです。それらを互いに交わらない円板へ描けば $G$ もplanarとなり矛盾します。従って $G$ は連結です。
$G$ にcut vertex $x$ があるとします。$G-x$ の成分を二群へ分け、それぞれへ $x$ を戻したgraphを $G_1,G_2$ とします。両者は $G$ より頂点数が少なく、障害を含まないのでplanarです。一点貼合せ補題により $G=G_1\cup G_2$ もplanarとなり矛盾します。従って $G$ は2-connectedです。
次に二頂点cut $\{x,y\}$ があるとします。$G-\{x,y\}$ の成分を二つの非空群へ分け、各群と $x,y$ からなる部分graphを $H_1,H_2$ とします。必要なら辺 $xy$ を加えて
$$ G_i=H_i+xy\qquad(i=1,2) $$
とします。
両方の $G_i$ がplanarなら、共通辺 $xy$ に沿う貼合せ補題で二つを貼り、最後に $xy\notin E(G)$ ならその辺を削除すれば $G$ のplane embeddingが得られます。従って少なくとも一方、例えば $G_1$ は非平面です。
$G_1$ は $G$ より頂点数が少ないので、最小性から $K_5$ または $K_{3,3}$ のsubdivision $S$ を含みます。$S$ が追加辺 $xy$ を使わなければ $S\subseteq G$ となり矛盾します。
$S$ が $xy$ を使う場合を考えます。$G$ は2-connectedなので、$H_2$ 内に内部頂点を $\{x,y\}$ の外にもつ $x$--$y$ path $P$ があります。実際、$H_2-\{x,y\}$ の任意の成分 $K$ は $x,y$ の両方に隣接しなければなりません。一方にしか隣接しなければ、その一頂点が $K$ を残りから分けるcut vertexになるからです。$K$ 内の連結pathへ両端辺を加えれば $P$ を得ます。
$S$ の辺 $xy$ を $P$ へ置き換えると、$P$ の内部は $H_1$ と交わらないため、同じKuratowski graphのsubdivisionが $G$ 内に得られます。これも矛盾です。従って二頂点cutはなく、$G$ は3-connectedです。□

$|X|\le1$ または $|Y|\le1$ なら、その一集合を含む退化しない短いarcを選び、補arcへ他方を入れるよう端点を取れるので1です。
$X=Y$ の場合、共通集合の大きさが2以下なら1、大きさが3なら3です。大きさが4以上なら、巡回順に異なる四点を選び、第一・第三を $x_1,x_2$、第二・第四を $y_1,y_2$ とみなせば2です。
残りでは $X\ne Y$ で両集合は少なくとも二点をもちます。必要なら $X,Y$ を交換して $x_1\in X\setminus Y$ を取ります。$x_1$ からcycleを二方向へ進み、それぞれ最初に出会う $Y$ の頂点を $y_1,y_2$ とします。$Y$ は二点以上なので、適切に同じ点を飛ばして最初の異なる点を取れば $y_1\ne y_2$ とできます。
$y_1,y_2$ が分ける二arcのうち $x_1$ を含む方を $P$、他方を $Q$ とします。選び方から $P$ の内部に $Y$ の頂点はありません。$Q$ の内部に $X$ の頂点 $x_2$ があれば、$x_1,y_1,x_2,y_2$ または逆向きの巡回順が得られて2です。そのような $x_2$ がなければ $X\subseteq V(P)$ であり、全ての $Y$ は $V(Q)$ に入るので1です。□

ある成分 $K$ に、例えば $a$ の隣接頂点がないと仮定します。$G-\{b,c\}$ を考えると、$K$ から外へ出る辺の端は $S$ にしかありませんが、$b,c$ は削除され、$a$ へは辺がありません。従って $K$ は残りから分離されます。これは二頂点 $\{b,c\}$ の削除でgraphが非連結になることを意味し、3-connected性に反します。$b,c$ についても同じです。□

$G/xy$ は4頂点以上です。3-connectedでないので、二頂点以下の集合 $Z$ が存在して $(G/xy)-Z$ は非連結です。
$q\notin Z$ なら、先に $G$ から $Z$ を削除してから $xy$ を縮約したgraphが $(G/xy)-Z$ です。しかし $|Z|\le2$ と3-connected性から $G-Z$ は連結であり、連結graphの一辺を縮約しても連結性は失われません。これは $(G/xy)-Z$ の非連結性に反します。従って $q\in Z$ です。
$Z=\{q\}$ なら
$$ (G/xy)-q=G-\{x,y\} $$
が非連結となり、やはり3-connected性に反します。従って $Z=\{q,z\}$ となる $z$ があり、
$$ (G/xy)-\{q,z\}=G-\{x,y,z\} $$
は非連結です。最後の隣接性は直前の3-separator補題を $S=\{x,y,z\}$ へ適用すれば得られます。□

全ての辺が非contractibleだと仮定します。各辺 $xy$ に対して、前補題から頂点 $z$ と $G-\{x,y,z\}$ の連結成分を選べます。そのような全ての組
$$ (xy,z,C) $$
のうち、$|V(C)|$ が最小のものを取ります。
3-separatorの隣接性から、$z$ は $C$ 内に隣接頂点 $v$ をもちます。辺 $zv$ も仮定により非contractibleなので、再び前補題から、ある頂点 $w$ に対して
$$ G-\{z,v,w\} $$
は非連結です。
$x,y$ は辺で結ばれています。従って $x,y$ のうち削除されていないものは同じ連結成分に入り、削除されたものがあっても、非連結graph $G-\{z,v,w\}$ には $x,y$ のどちらも含まない連結成分 $D$ が少なくとも一つあります。詳しくは、$w\notin\{x,y\}$ なら辺 $xy$ により両者は同じ成分に入るので別成分を取り、$w=x$ または $w=y$ なら残る一方を含まない別成分を取ります。
三頂点separator $\{z,v,w\}$ の隣接性から、$v$ は $D$ 内に隣接頂点をもちます。任意の $b\in V(D)$ を取ると、$D$ の連結性により $b$ からその隣接頂点へ $D$ 内のpathがあり、最後に辺を一本加えて $v$ へ至ります。このpathは $x,y,z$ を通りません。実際 $D$ は $x,y$ を含まず、定義から $z$ も含みません。
従って $b$ と $v$ は $G-\{x,y,z\}$ で同じ連結成分に属します。$v\in C$ だったので $b\in C$ です。$b$ は任意だったから
$$ V(D)\subseteq V(C). $$
しかも $D$ は非空で、$v\notin D$ かつ $v\in C$ なので真の包含
$$ \varnothing\ne V(D)\subsetneq V(C) $$
です。しかし $(zv,w,D)$ も最初に最小化した組の候補であり、$|V(D)|<|V(C)|$ は最小性に反します。
従って全辺が非contractibleという仮定は偽であり、少なくとも一辺 $e$ で $G/e$ は3-connectedです。□

face境界walkが頂点 $a$ を二度通るとします。$a$ の十分小さい円板内で、二回の通過に対応する四本のedge-endは二組に分かれます。face内に二回の通過位置を結ぶarcを取り、円板内で $a$ だけを通るよう閉じると、graphと $a$ だけで交わる単純閉曲線が得られます。
境界walkの二つの区間にはそれぞれ辺があるため、この閉曲線の両側にgraphの頂点または辺があります。従って $a$ を削除すると両側を結ぶpathがなくなり、graphは非連結です。これは2-connected性に反します。よって境界walkは頂点を重複せずcycleです。□

円板をhomeomorphismで長方形へ移し、$P$ を上辺、$Q$ を下辺に対応させます。$u$ を上辺のすぐ内側、$v$ を下辺のすぐ内側へ置きます。
$u$ から $P$ 上の点への辺は、$u$ を共通端とする扇形として互いの巡回順を保って上半分へ描けます。同様に $v$ から $Q$ 上の点への辺を下半分へ描けます。二つの扇形を十分境界近くへ取れば中央帯が空くので、そこへ $uv$ を描けます。上・下・中央の内部は互いに交わらず、所要の描画を得ます。□

branch vertexの二部を
$$ \{u,y_1,y_2\},\qquad \{v,x_1,x_2\} $$
とします。$u$ から反対側への三pathは $uv,ux_1,ux_2$、$v$ へ入る残る二pathは $y_1v,y_2v$ です。
$C$ を四つの指定点で切ると、連続する指定点を結ぶ四本の内部頂点非共有arcが得られます。それらは
$$ y_1\leadsto x_1,\quad y_1\leadsto x_2,\quad y_2\leadsto x_1,\quad y_2\leadsto x_2 $$
の四pathをちょうど与えます。合計九pathはbranch vertex以外で交わらないので、$K_{3,3}$ subdivisionです。□

branch vertexを $u,v,a,b,c$ とします。$u,v$ と $a,b,c$ の間の六辺および $uv$ が七本のbranch pathです。cycle $C$ を $a,b,c$ で切って得る三arcが、$a,b,c$ 間の三辺に対応するbranch pathになります。三arcの内部は互いに交わらず、新頂点 $u,v$ を含みません。従って十組全てを内部頂点非共有pathで結ぶ $K_5$ subdivisionです。□

頂点数 $n$ について帰納します。$n=4$ では、3-connected simple graphは $K_4$ でありplanarです。
$n\ge5$ とし、contractible-edge theoremで $e=uv$ を、$H=G/e$ が3-connectedとなるよう選びます。縮約障害持上げ補題の対偶により $H$ も二障害を含みません。帰納法から $H$ はplanarです。縮約頂点を $w$ とします。
plane embeddingから $w$ と接続辺を削除すると $H-w$ が残ります。$H$ は3-connectedなので $H-w$ は2-connectedです。$w$ が置かれていた領域を含むfaceの境界は、face境界補題によりcycle $C$ です。$w$ の全隣接頂点は $C$ 上にあります。
元の $G$ で $u$ に接続していた $C$ 上の頂点集合を $X$、$v$ に接続していた集合を $Y$ とします。共通隣接頂点は両方へ入れます。cyclic two-set lemmaを適用します。
場合1なら、separated attachments補題により $H-w$ の該当face内へ $u,v$ と全接続辺を戻せるので $G$ はplanarです。
場合2なら、alternating attachments補題により $G$ は $K_{3,3}$ subdivisionを含み、仮定に反します。場合3なら、three common attachments補題により $G$ は $K_5$ subdivisionを含み、やはり反します。
従って障害のない場合に残るのは場合1だけで、$G$ はplanarです。帰納法が閉じます。□

反例があれば頂点数最小の反例 $G$ を取ります。最小反例の3-connected性補題から $G$ は3-connectedです。直前の定理から $G$ はplanarとなり反例であることに矛盾します。□

$G$ がplanarなら、部分graphもplanarです。「Euler公式の限界とKuratowskiの定理」で証明した通り、$K_5,K_{3,3}$ は非平面であり、辺の分割・division vertexの除去は平面性を変えません。従ってplanar graphは二つのsubdivisionを含みません。
逆に $G$ が二つのsubdivisionを含まないなら、直前の系により $G$ はplanarです。両方向が示されたのでKuratowski theoremが従います。□

両端が $C$ 上にあるchordは定義1のbridgeを一つ作ります。それ以外の辺は少なくとも一端が $H-V(C)$ にあり、その端を含むただ一つの連結成分 $K$ によって定義2のbridgeへ入ります。
異なる成分は頂点を共有しません。また二つの異なるchordは辺として別で、内部頂点をもちません。従って異なるbridgeが共有できるのは $C$ 上の端、すなわちattachmentだけです。□

$B$ がchordなら、その一辺がpathです。成分型なら、$a,b$ から $H-V(C)$ の同じ連結成分 $K$ へ入る辺を一本ずつ取ります。$K$ は連結なので、それらの $K$ 側端を結ぶwalkがあり、閉じた回り道を消してpathにできます。両端の二辺を加えると、内部頂点が全て $K$ に属する $a$--$b$ pathになります。□

第一の場合を仮定します。bridge内部のattachment path補題により、同じ円板側に $a_1$--$b_1$ path $P_1$ と $a_2$--$b_2$ path $P_2$ を取れます。異なるbridgeなので両pathの内部は共有されません。
$P_1$ と $C$ 上の $a_1$--$b_1$ arcの一方を合わせると単純閉曲線になります。$a_2,b_2$ は $C$ 上で交互に位置するため、この閉曲線の反対側にあります。従って $a_2$--$b_2$ path $P_2$ は閉曲線を横切らなければならず、plane描画に反します。
第二の場合、共有attachmentを $a,b,c$ とします。第一bridgeの $C$ 外成分は連結なので、その内部に、ある内部頂点 $q$ から $a,b,c$ へ向かう三本のpathで、$q$ 以外に頂点を共有しないものを取れます。実際、成分内で三attachmentへの接続を含む辺数最小の連結部分graphを取ればtreeであり、三端へのpathの共通部分を削って最初の分岐点を $q$ にできます。$q$ は $C$ 外にあります。
この三本のarcは円板を三領域へ分けます。polygonal Jordan曲線定理を二本ずつのarcと対応する $C$-arcへ適用すれば、各領域の境界が $a,b,c$ のうち二点だけを含むことを順に確認できます。第二bridgeの $C$ 外部分は連結で第一bridgeの内部と交わらないため、一つの領域に全て入らなければなりません。しかしどの一領域の境界にも三attachment全ては現れず、第二bridgeは $a,b,c$ 全てへ到達できません。矛盾です。従って三attachment共有も同じ側では不可能です。□

各 $C$-bridgeを、描画で $C$ の内側にあるか外側にあるかにより二群へ分けます。前補題によりconflictするbridgeは同じ群へ入れないので、これは $\Gamma_C$ のproper 2-coloringです。□

plane drawingを一つ固定します。頂点または辺の削除は、対応する点またはarcを描画から消すだけなので交差を作りません。
辺 $uv$ の縮約では、$uv$ を表すarcに沿って $u$ を $v$ へ連続的に滑らせます。十分細い $uv$ の近傍を取れば、その内部には $uv$ と両端付近の接続arc以外がありません。従って移動と接続arcの短縮をこの近傍内で行え、他の辺との交差を作りません。縮約によりloopまたは平行辺が生じても、それらは同じ細い近傍内へ描けます。よって一回のminor操作はplanarityを保ち、有限回の合成もplanarityを保ちます。□

$G$ がplanarなら、前補題により全てのminorもplanarです。第08・09章で $K_5$ と $K_{3,3}$ は非平面と証明したので、これらをminorとして含むことはできません。
逆に、$G$ が $K_5,K_{3,3}$ のどちらもminorとして含まないとします。もし $G$ が非平面なら、本章で証明したKuratowski定理により、$G$ は $K_5$ または $K_{3,3}$ のsubdivisionを部分graphとして含みます。そのbranch pathを縮約すれば対応する $K_5$ または $K_{3,3}$ minorが得られ、仮定に反します。従って $G$ はplanarです。□

縮約後のpathが局所的に $x-w-y$ と進み、$xw$ が $xu$、$wy$ が $vy$ から生じたとします。元のgraphでは
$$ x-u-v-y $$
と辺 $uv$ を挟みます。$w$ は元のsimple pathで一度だけ現れたので、新しく挿入した $u,v$ は他のpath部分に現れません。他のbranch pathも $w$ を使わないため、内部頂点非共有性を保ってsubdivisionを持ち上げられます。□

二部を
$$ \{u,c,d\},\qquad \{v,a,b\} $$
とします。$u$ は $v,a,b$ 全てと隣接し、$c$ と $d$ はそれぞれ $v,a,b$ 全てと隣接します。従って両部の九組を結ぶ辺が全てあり、それらだけを残せば $K_{3,3}$ です。□

巡回順なので、末尾の $U$ と先頭の二つの $U$ は巡回的に連続しています。残る二つの $V$ も連続です。従って二群はそれぞれ一つの巡回区間をなし、固定embeddingでの頂点分裂条件から分裂可能です。線形表示の両端が巡回順では隣接する点に注意が必要です。□

$a$--$b$ pathと、円周上の二つの $a$--$b$ arcの一方を合わせると単純閉曲線になります。$c,d$ は円周上で $a,b$ と交互に置かれているため、この閉曲線の反対側にあります。従って $c$--$d$ pathは単純閉曲線を横切らなければなりません。横切り点は円周上の端点ではなく二pathの内部に生じるので、内部頂点非共有または交差なしという条件に反します。□

$C$ は単純閉曲線なので平面を内側と外側へ分けます。各 $C$-bridgeは連結で、$C$ 以外の部分は交差なし描画の内側または外側の一方に全て入ります。内側bridgeを色0、外側bridgeを色1とします。
同色の二bridgeがconflictすれば、同じ側に描かれたbridgeはconflictしないという補題に反します。従ってconflict edgeの両端は必ず異色であり、これはproper 2-coloringです。□

縮約持上げ補題は「縮約後に障害があれば元にもある」を保証するので、障害なしという仮定を縮約後へ渡せます。しかし帰納法を3-connected graphの範囲で続けるには、縮約後も3-connectedとなる辺を選ばなければなりません。
任意の辺を縮約して2-connected以下へ落ちると、縮約頂点を削除したface境界がcycleになる保証を失い、cyclic two-set lemmaによる分裂分類を適用できません。contractible-edge theoremは、帰納法の構造仮定を保つ辺の存在を保証するために必要です。□

まず $S$ に属さない全ての辺と頂点を削除して $S$ だけを残します。$S$ の各branch pathについて、内部頂点がなくなるまでpath上の辺を縮約します。異なるbranch pathの内部頂点は互いに共有されないので、一つのpathで行う縮約は他のbranch pathのbranch vertexを同一視しません。
全九本のbranch pathを一本の辺へ縮約すると、六つのbranch vertexが残り、二部の各三頂点間を結ぶ九辺が得られます。これは $K_{3,3}$ です。従って $K_{3,3}$ subdivisionを含むことから $K_{3,3}$ minorを含むことが、明示的なminor操作列として示されました。□