クラトフスキーの定理の証明(3)誘導部分グラフから2-連結の証明

グラフ理論において、あるグラフが平面的であるかどうかを見極めるための重要な定理、

クラトフスキーの定理

の証明第3弾です。

前回までの記事を読まれていない方は、まずそちらからご覧ください。

さて、今回は前回に引き続き、最小の非平面的グラフが3-連結になることを証明していきます。

スポンサーリンク
レクタングル(大)広告

■ 誘導部分グラフ

あるグラフから特定の頂点を指定し、それらの頂点に両端が接続する辺を取り出した部分グラフのことです。

指定されなかった頂点を辺ごと取り除いた部分グラフ」と考えても差し支えありません。

誘導部分グラフ

■ 最小の非平面的グラフが 2-連結 であることの証明

□ 最小の非平面的グラフ \(G\) が 2-連結でない、すなわち 1-連結 であると仮定します。

□ 仮定より、それを取り除くことで \(G\) が非連結となるような頂点 \(v\) が存在します。

□ \(v\) を取り除いた非連結グラフの連結成分の1つを \(C\) とします。

□ \(G\) は最小の非平面的グラフなので、\(C\) と \(v\) の誘導部分グラフと、

\(G-C\) と \(v\) の誘導部分グラフはどちらも平面的になります。

□ すると、双方の \(v\) を合体させることで、\(G\) も平面に描くことができるので、

\(G\) が非平面的であることに矛盾します。

2-連結の証明

■ 最小の非平面的グラフが 3-連結 であることの準備

\(G\) を 2-連結の非平面的グラフ、グラフを切断する 2頂点を \(x,y\)、切断されたグラフの連結成分の1つを \(C\) とする。
その時、\(C\) と \(x,y\) の誘導部分グラフに辺 \(xy\) を加えたものが非平面的になるような \(C\) が存在する。

▽ 証明

背理法と帰納法を用いて証明します。

□ \(G\) を \(x,y\) で切断した非連結グラフの連結成分を \(C_1,\cdots,C_k\) とします。

□ \(C_i\) と \(x,y\) の誘導部分グラフに辺 \(xy\) を加えたグラフを \(G_i\) とします。

□ \(G_1,\cdots,G_k\) がすべて平面的であると仮定します。

・ 仮定より、\(G_1\) は平面に(辺の交差なしで)描けます。

・ \(G_i\) が平面に描けるとき、\(G_{i+1}\) は \(G_i\) の辺 \(xy\) を含む面の中に描くことができ、

2つのグラフを辺 \(xy\) で合体させると、やはり平面グラフになります。

□ このようにして、\(k\) 個のグラフを次々に合体させていくと、\(G\) 全体も平面に描くことができるので、

\(G\) が非平面的であることに矛盾します。

3-連結の準備(1)

3-連結の準備(2)

■ まとめ

だんだん難しくなってきましたね。

私も初めてこの証明を読んだときは、何を言っているのかさっぱり分からなくて苦労しました。

「もっと図を使って説明してくれれば理解できるのに…」

とその時思ったものです。

ですので、今回の記事では、できるだけ図を多用して視覚的にイメージできるよう配慮したつもりです。

次回は、いよいよ最小の非平面的グラフが 3-連結であることを証明します。

乞うご期待。

次の記事 → クラトフスキーの定理の証明(4)3-連結の証明と縮約・拡逆

関連コンテンツユニット
スポンサーリンク
レクタングル(大)広告
レクタングル(大)広告

シェアする

  • このエントリーをはてなブックマークに追加

フォローする