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

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

 

クラトフスキーの定理

 

の証明第6弾です。

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

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

 

前回と前々回の記事では、

従属命題 A

従属命題 B

 

という2つの従属命題を証明しました。

 

今回はその従属命題を用いて、いよいよクラトフスキーの定理の証明を完結させていこうと思います。

■ 凸多角形

凸多角形 とは、どの 2頂点を結ぶ線分も、その多角形の外に出ることがないようなものです。

凸多角形では、どの内角の大きさも \(180^\circ\) 未満になっています。

 

■ 凸埋め込み

平面的グラフ \(G\) の 凸埋め込み とは、すべての辺がまっすぐな線分で、

一番外側を除くすべての面が凸多角形であるような平面グラフです。

 

■ 3-連結グラフが凸埋め込みを持つことの証明

これは、\(G\) が平面的であることを示し、こうしてクラトフスキーの定理の証明が完結します。

上の命題を頂点数についての帰納法で証明します。

帰納法の基礎

最小の 3-連結グラフは 4個の頂点を持ちます。

 

帰納法のステップ

□ \(k\) を4以上の自然数、頂点数 \(|V|=k\) のクラトフスキー部分グラフを含まない 3-連結グラフを \(G_k\) とします。

□ 従属命題 A より、\(|V|=k+1\) のとき、縮約しても 3-連結になるような辺 \(e\) が存在します。

□ 従属命題 B より、クラトフスキー部分グラフを拡逆しても、クラトフスキー部分グラフを含まないグラフは生成できません。

以上のことから、\(G_{k+1}\) は \(G_k\) を拡逆して生成可能であることが分かります。

□ \(G_k\) が平面的であるとき、\(G_{k+1}\) も平面的であるかどうかを調べていきます。

□ \(G_k\) において、拡逆を行う頂点を \(z\) とします。

□ \(G_k\) は 3-連結なので、\(z\) を取り除くと 2-連結となり、

\(z\) は多角形の中に存在することになります。

□ \(z\) を拡逆したとき、複製元となる頂点を \(x\)、複製先となる頂点を \(y\) とします。

□ また、\(x\) に隣接した多角形上の頂点を \(x_1,\cdots,x_n\)、\(y\) に隣接した頂点を \(y_1,\cdots,y_n\) とします。

■ まとめ

まだ帰納法の途中ですが、記事が長くなってきたので続きは次回にしたいと思います。

ここまで6回にわたり連載してきたクラトフスキーの定理の証明もいよいよ最終回。

クラトフスキー部分グラフを含まない 3-連結グラフは凸埋め込みを持つ（＝平面的である）ことを示し、

非平面的グラフを生成するには、やはりクラトフスキー部分グラフを含めなければならないという結論を導きます。

読者と一緒に感動の結末を迎えたいので、次回の記事もどうぞよろしくお願いいたします。

 

次の記事　→　クラトフスキーの定理の証明（7）そして完結へ