クラトフスキーの定理の証明(5)3-連結は平面的を証明する準備

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

クラトフスキーの定理

の証明第5弾です。

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

前回までの説明で、クラトフスキー部分グラフを含まない最小の非平面的グラフが 3-連結であることを示しました。

次に、そのようなグラフは平面的グラフになってしまうことを証明するのですが、

その準備として、2つの従属命題を証明します。

今回は、その続きです。

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

■ 縮約によってクラトフスキー部分グラフが生じないことの証明(続き)

□ グラフ \(G\) の中の辺 \(e\) を縮約して得られたグラフを \(G_e\)、縮約してできた頂点を \(v_e\) とします。

□ もし、\(v_e\) がクラトフスキー部分グラフ \(H\) の頂点にあたる場合、

\(v_e\) から辺を奪わずに拡逆すると、\(H\) が \(G\) の部分グラフとなって矛盾するのは明らかです。

縮約とクラトフスキー部分グラフ3

□ したがって、複製された頂点が \(v_e\) から辺を奪って拡逆する場合を考えますが、

いずれのパターンでも、やはり \(H\) が \(G\) の部分グラフとなって矛盾してしまいます。

□ ここで、そのすべてのパターンを解説すると、説明が長くなってしまうので割愛しますが、

結論だけ書いておくと、

1. \(K_5\) において 1辺を奪って拡逆 → \(G\) が \(K_5\) の細分を含む
2. \(K_5\) において 2辺を奪って拡逆 → \(G\) が \(K_{3,3}\) を含む
3. \(K_5\) において 3辺を奪って拡逆 → \(G\) が \(K_5\) の細分を含む
4. \(K_5\) において 4辺を奪って拡逆 → \(G\) が \(K_5\) を含む
5. \(K_{3,3}\) において 1辺を奪って拡逆 → \(G\) が \(K_{3,3}\) の細分を含む
6. \(K_{3,3}\) において 2辺を奪って拡逆 → \(G\) が \(K_{3,3}\) の細分を含む
7. \(K_{3,3}\) において 3辺を奪って拡逆 → \(G\) が \(K_{3,3}\) を含む

となります。

参考までに、1. と 2. のパターンについて、図を載せておきます。

縮約とクラトフスキー部分グラフ4


縮約とクラトフスキー部分グラフ5

■ 3-連結グラフを縮約しても 3-連結になることの証明

\(G\) を位数 5 以上の 3-連結グラフとする。その時、縮約しても 3-連結になるような辺 \(e\) が存在する。

□ \(G\) は位数 5 以上の 3-連結グラフで、\(G\) のいかなる辺を縮約しても 3-連結にならないものとします。

□ \(G\) の中の辺 \(e\) を縮約して得られたグラフを \(G_e\)、縮約してできた頂点を \(v_e\) とします。

□ \(G_e\) は 3-連結ではないので、\(v_e\) と \(z_e\) を取り除くことで

\(G_e\) が非連結になるような \(z_e\) が存在します。

このことは、辺 \(e\) の端点を \(x,y\) とすると、\(G\) が \(x\) と \(y\) と \(z_e\) を取り除くことで非連結になるということです。

縮約と3-連結1

□ \(x,y,z_e\) の3点で \(G\) を非連結にしたとき、連結成分 \(C\) のサイズ(辺の数)が最大になるように \(x,y\) を選びます。

この時、もう1つの連結成分は \(C’\) とします。

□ \(z_e\) と \(C’\) 上の頂点 \(u\) をつなぐ辺を \(f\) とします。

縮約と3-連結2

□ 仮定より、\(G\) から \(z_e,u,z_f\) の3点を取り除いたとき、

\(G\) が非連結になるような \(z_f\) が存在します。

なぜなら、そのような \(z_f\) が存在しないと、辺 \(f\) を縮約したとき、

グラフが 3-連結になってしまうからです。

□ しかし、\(G\) から \(z_e,u,\) の2点を取り除いたとき、残されたグラフにはハミルトンサイクルが存在するため、

残り1点を取り除いてグラフを非連結にできるような \(z_f\) は存在せず、

仮定は矛盾していることになります。

■ まとめ

この辺の証明は内容が難しく、読者に説明がうまく伝わっているか不安です。

記事の中で分からない部分があれば、コメント欄から遠慮なくご質問ください。

今回の記事では、クラトフスキー部分グラフを拡逆しても、やはりクラトフスキー部分グラフになることを、

あらゆるパターンで確認するのが大変でした。

この事実は、

縮約するとクラトフスキー部分グラフになるようなグラフは非平面的グラフである(ワグナーの定理

につながっているのかもしれません。

クラトフスキーの定理の証明も、ようやく出口が見えてきました。

最後までお付き合いいただければ幸いです。

次の記事 → クラトフスキーの定理の証明(6)3-連結は凸埋め込みを持つ証明

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

シェアする

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

フォローする