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

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

クラトフスキーの定理

の証明第5弾です。

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

• クラトフスキーの定理の証明（1）グラフ理論用語と定理の紹介
• クラトフスキーの定理の証明（2）点連結度から1-連結の証明まで
• クラトフスキーの定理の証明（3）誘導部分グラフから2-連結の証明
• クラトフスキーの定理の証明（4）3-連結の証明と縮約・拡逆

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

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

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

今回は、その続きです。

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

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

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

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

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

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

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

結論だけ書いておくと、

となります。

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

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

□ $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$ を取り除くことで非連結になるということです。

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

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

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

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

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

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

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

□ $C$ と $x,y$ の誘導部分グラフは連結で、仮にこの部分グラフが $z_f$ を

含んでいた場合、$z_f$ を削除しても部分グラフを非連結にすることはできません。

もし、非連結になるなら、$G$ から $z_e,z_f$ の2点を削除しても非連結になり、

$G$ が3連結であることに矛盾するからです。

□ したがって、$z_f$ は $C’$ に含まれていることになりますが、その場合、

$z_e,u,z_f$ を削除してできた非連結グラフは、$C$ よりも大きな連結成分を持つ

ことになり、$C$ のサイズが最大であるという仮定に矛盾するわけです。

■ まとめ

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

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

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

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

この事実は、

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

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

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

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