5-2 Euler公式の限界とKuratowskiの定理
前提知識：平面グラフ
辺数評価をすり抜ける非平面グラフ
「平面グラフ」では、simple planar graphが
$$
e\le3v-6
$$
を満たすことを示しました。しかしこれは必要条件にすぎません。
$K_{3,3}$ の各辺の途中へ新頂点を一つずつ置くと、頂点数は6から15、辺数は9から18になります。上界
$$
18\le3\cdot15-6=39
$$
を十分に満たします。それでも平面には描けません。途中の次数2頂点を消して二本の辺をつなげば、$K_{3,3}$ の平面描画が得られてしまうからです。
つまり平面性の障害は辺の密度だけでなく、「辺を長いpathへ引き伸ばしても残る構造」にあります。
辺の分割とsubdivision
グラフ $G$ の辺 $uv$ を削除し、新しい頂点 $w$ と二辺 $uw,wv$ を加える操作を辺の分割という。
辺の分割を有限回行って得られるグラフを $G$ の細分グラフ|subdivisionという。$G$ と $H$ が共通のsubdivisionをもつとき、両者は同相なグラフ|homeomorphicであるという。
一つの辺を何度も分割することは、その辺を内部頂点が互いに異なるpathへ置き換えることです。元の頂点をbranch vertex、途中に入れた次数2頂点をdivision vertexと呼びます。
グラフ $G$ がplanarであるための必要十分条件は、$G$ の任意のsubdivisionがplanarであることである。また、一つでもplanarなsubdivisionがあれば $G$ はplanarである。
$G$ のplane描画があれば、分割する辺の曲線上に新頂点を置くだけで、辺を交差させずに分割後のグラフを描けます。これを繰り返せば任意のsubdivisionがplanarです。
逆に、$G$ のsubdivision $H$ がplane描画をもつとします。分割で加えられた次数2頂点 $w$ の近くでは、二辺 $uw,wv$ は $w$ 以外で交わらない二本のarcです。その二本を一つのarcとして滑らかにつなぎ、$w$ を消します。この操作は十分小さい近傍内で行えるため、他の辺との交差を作りません。
division vertexを一つずつ消すと $G$ のplane描画を得ます。従って $G$ はplanarです。□
この定理により、$K_5$ または $K_{3,3}$ のsubdivisionはすべて非平面です。
subdivisionを部分グラフとして含む
グラフ $G$ が、グラフ $H$ のsubdivisionと同型な部分グラフを含むとき、$H$ は $G$ の位相的マイナー|topological minorであるという。
別の言い方をすると、$H$ の各頂点を $G$ の相異なるbranch vertexへ送り、$H$ の各辺を、それらを結ぶpathへ置き換えます。異なる辺に対応するpathはbranch vertex以外の内部頂点を共有してはいけません。
グラフ $G$ が $K_5$ または $K_{3,3}$ をtopological minorとして含むなら、$G$ は非平面である。
$G$ がplanarだと仮定します。planar graphの部分グラフは、不要な辺と頂点をplane描画から削ればplanarです。従って $G$ に含まれる $K_5$ または $K_{3,3}$ のsubdivisionもplanarになります。
subdivisionと平面性の定理から、元の $K_5$ または $K_{3,3}$ もplanarになってしまいます。しかし「平面グラフ」で両者が非平面であることを証明しました。矛盾です。□
この方向だけでも、具体的な非平面性証明に強力です。重要なのは、見た目ではなくbranch vertexと内部で交わらないpathを明示することです。
辺の縮約とminor
辺 $uv$ の辺の縮約|縮約とは、$u,v$ を一つの新頂点へ同一視し、それらに接続していた辺を新頂点へ接続し直す操作をいう。生じたloopは削除し、平行辺は単純グラフとして扱う場合一本にまとめる。
頂点削除、辺削除、辺縮約を有限回行って $H$ が得られるとき、$H$ は $G$ のグラフマイナー|minorであるという。
planar graphから頂点削除、辺削除、辺縮約で得られるグラフはplanarである。
頂点や辺の削除はplane描画から対応する点・曲線を消すだけなので平面性を保ちます。
辺 $uv$ の縮約では、plane描画上のarc $uv$ に沿って頂点 $u$ を $v$ へ連続的に動かします。$uv$ の内部は他の頂点や辺に触れないので、十分細い近傍の中で、$u$ に接続する辺の端だけを一緒に引き寄せられます。$u$ と $v$ が重なった後にloopを消し、平行辺を一本へまとめても交差は生じません。
各操作が平面性を保つため、有限回の操作で得られるminorもplanarです。□
$G$ が $K_5$ または $K_{3,3}$ をminorとして含むなら、$G$ は非平面である。
$G$ がplanarなら、その全minorも前定理によりplanarです。しかし $K_5,K_{3,3}$ は非平面なので、それらをminorとしてもつことはできません。対偶を取れば主張を得ます。□
topological minorなら、各辺を置き換えたpathを縮約して元のグラフを得られるためminorでもあります。逆は一般には成り立ちません。minorでは、一つのbranch vertexに対応する部分を連結な頂点集合まで膨らませられるからです。
Kuratowskiの定理が主張すること
ここまでで「$K_5$ または $K_{3,3}$ のsubdivisionを含めば非平面」という方向を完全に証明しました。Kuratowskiの定理は、逆方向も成り立つと主張します。
有限グラフ $G$ がplanarであるための必要十分条件は、$G$ が $K_5$ と $K_{3,3}$ のいずれもtopological minorとして含まないことである。
十分性、すなわち「二つの障害を含まなければplane描画が存在する」の証明は長く、平面内のbridge配置を整理する複数の補題を必要とします。この第一周では定理を判定規則として使用しません。完全証明は「平面性判定の構造」で、次の順に独立して行います。
- 非平面グラフから辺数最小の反例を取る。
- 最小反例が3-connectedに近い構造をもつことを示す。
- cycleに対するbridgeと、そのattachmentの交差を調べる。
- 交互配置するbridgeから $K_{3,3}$ subdivisionを作る。
- 交互配置しない場合からplane embeddingを組み立て、最小性に反する。
従って本章で証明済みとして使ってよいのは「障害を見つければ非平面」という方向です。逆方向を用いる箇所は「平面性判定の構造」以後に限定します。
Wagnerの見方との違い
minorを使った対応定理は次の形です。
有限グラフがplanarであるための必要十分条件は、$K_5,K_{3,3}$ をminorとして含まないことである。
これはWagnerの定理です。Kuratowskiはsubdivision、Wagnerはminorを使います。結論は似ていますが、一般のグラフ $H$ について「$H$ をminorに含む」と「$H$ subdivisionを含む」は同じではありません。平面性では二つの特別な障害がどちらの言葉でも完全な特徴づけを与えます。
Wagnerの定理も本章では推論に使用しません。「平面性判定の構造」のKuratowski証明後に、縮約との対応を補論として証明します。
障害を手で見つける方法
具体的なグラフから $K_5$ subdivisionを探すなら、次数4以上のbranch vertex候補を5個選び、それぞれの組を結ぶ10本のpathを探します。$K_{3,3}$ なら、左右3個ずつのbranch vertex候補と、左右の各組を結ぶ9本のpathを探します。
確認事項は三つです。
- branch vertexはすべて相異なる。
- 各pathの内部にbranch vertexを含まない。
- 異なるpathの内部頂点は互いに交わらない。
単に「$K_{3,3}$ のように見える」だけでは不十分です。pathを辺へ縮めたとき、本当に目的のグラフになることを確認します。
例――分割された $K_{3,3}$
左右のbranch vertexを
$$
X=\{a,b,c\},\qquad Y=\{1,2,3\}
$$
とします。九つの組 $(x,i)\in X\times Y$ ごとに新頂点 $w_{xi}$ を置き、二辺
$$
xw_{xi},\qquad w_{xi}i
$$
を加えます。
各 $x$-$i$ pathは $x,w_{xi},i$ で、内部頂点 $w_{xi}$ は九つすべて異なります。従ってこのグラフ全体が $K_{3,3}$ のsubdivisionであり、前に証明した系だけで非平面だと結論できます。辺数上界は満たしますが、構造的障害は消えていません。
最小非平面性と辺の削除
非平面グラフ $G$ が辺極小非平面的グラフ|edge-minimal nonplanarであるとは、任意の辺 $e$ に対して $G-e$ がplanarであることをいう。
任意の有限非平面グラフから、平面性を回復しない限り辺を削り続ければedge-minimal nonplanar部分グラフが得られます。この有限降下は簡単ですが、「その最小障害が必ず $K_5$ または $K_{3,3}$ のsubdivisionを含む」と示す部分がKuratowski定理の核心です。
edge-minimal nonplanar graph $G$ はbridgeをもたない。
bridge $e=uv$ があると仮定します。$G-e$ は二つの側へ分かれます。edge-minimal性により $G-e$ はplanarなので、各連結成分を別々の小円盤内にplane描画できます。
$u$ を含む成分と $v$ を含む成分の描画を離して置き、両者の外面に $u,v$ が来るよう描画を反転・変形します。二つの円盤の外側を通るarcで $u$ と $v$ を結べば、他の辺と交差せずにbridge $e$ を戻せます。すると $G$ がplanarになり矛盾です。従ってbridgeはありません。□
演習
$K_5$ の各辺を任意回分割して得たグラフで、次数4の頂点はいくつあり、それ以外の新頂点の次数はいくつか。
元の $K_5$ の五頂点は各次数4です。辺を分割しても元の頂点に接続する辺が途中で切り替わるだけで、次数は変わりません。
分割で加えた新頂点は、置き換えたpathの前後の二頂点とのみ隣接するため次数2です。従って次数4のbranch vertexが5個あり、全division vertexの次数は2です。□
$H$ が $G$ のtopological minorなら、$H$ が $G$ のminorでもあることを証明せよ。
$G$ の部分グラフ $S$ が $H$ のsubdivisionと同型だとします。まず $G$ から $S$ に属さない頂点と辺を削除して $S$ を得ます。
$H$ の各辺を置き換えたpathで、内部のdivision vertexに接続する辺を順に縮約します。異なるpathは内部頂点を共有しないため、この操作は他の辺対応を壊しません。全pathを一本の辺へ戻すと $H$ が得られます。従って $H$ はminorです。□
非平面グラフへ頂点や辺を追加して得たグラフも非平面であることを示せ。
追加後のグラフを $G'$、元の非平面グラフを $G$ とします。$G$ は $G'$ の部分グラフです。もし $G'$ がplanarなら、そのplane描画から追加した頂点と辺を削除して $G$ のplane描画が得られます。これは $G$ の非平面性に反します。従って $G'$ も非平面です。□
Petersen graphを、外側の5-cycle $v_0v_1\cdots v_4v_0$、内側の頂点 $u_0,\ldots,u_4$、spoke $v_iu_i$、内側の辺 $u_iu_{i+2}$（添字は5を法とする）で定める。五本のspoke $v_iu_i$ をすべて縮約すると得られるグラフを記述せよ。
各spokeを縮約し、$v_i,u_i$ を一頂点 $w_i$ にまとめます。外側の辺から $w_iw_{i+1}$ が、内側の辺から $w_iw_{i+2}$ が得られます。
5頂点では、相異なる二頂点の添字差は5を法として $\pm1$ または $\pm2$ のいずれかです。従ってすべての二頂点間に辺があり、得られる単純グラフは $K_5$ です。よってPetersen graphは $K_5$ minorをもち、非平面です。□
$K_5$ の各辺を $r\ge1$ 回分割したグラフ $G_r$ の頂点数と辺数を求め、$e\le3v-6$ を満たすことを確認せよ。それでも非平面である理由を述べよ。
$K_5$ は5頂点10辺です。一辺ごとに $r$ 個の新頂点を加えるので
$$
v=5+10r.
$$
一辺は $r+1$ 本へ分かれるので
$$
e=10(r+1)=10r+10.
$$
右辺は
$$
3v-6=3(5+10r)-6=30r+9.
$$
$r\ge1$ なら
$$
10r+10\le30r+9
$$
です。しかし $G_r$ は $K_5$ のsubdivisionそのものなので、subdivisionと平面性の定理により非平面です。□
頂点削除についても最小、すなわち任意の頂点を削るとplanarになる非平面グラフ $G$ を考える。$G$ に次数0または1の頂点が存在しないことを示せ。
次数0の頂点 $v$ があれば、$G-v$ のplane描画へ、どの辺とも交わらない位置に孤立頂点 $v$ を戻せます。従って $G$ もplanarとなり矛盾です。
次数1の頂点 $v$ と唯一の隣接頂点 $u$ があれば、$G-v$ のplane描画で $u$ の十分小さい近傍に $v$ を置き、短いarc $uv$ を描けます。他の辺と交差しません。やはり $G$ がplanarとなり矛盾です。従って最小次数は少なくとも2です。□
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
