数学 › グラフ理論 › Kuratowski の定理

辺極大なグラフは 2 点で貼り合わされている

補題 6.3（「Kuratowski の定理」§6）・ ✓公理まで証明済み

$G$ を、頂点数 4 以上で Kuratowski 部分グラフをもたない辺極大なグラフとし、3-連結でないとする。このとき、隣接する 2 頂点 $x,y$ と、 $G$ の誘導部分グラフ $G_1,G_2$ で、次を満たすものがある。

$G=G_1\cup G_2$ 、 $V(G_1)\cap V(G_2)=\{x,y\}$ で、 $A_i=V(G_i)\setminus\{x,y\}$ は空でなく、 $A_1$ と $A_2$ を結ぶ辺はない。
$x$ も $y$ も、 $A_1$ と $A_2$ のそれぞれに隣接点をもつ。
$G_1$ と $G_2$ は、Kuratowski 部分グラフをもたない辺極大なグラフである。

本文で読む（証明と前後の説明）→

閉包の状態

✓ 公理まで証明済み

証明が使う定理を前提としてたどると、Rikai の中の証明だけで定義・公理（物理では基本仮定）までつながっています（前提の定理類 2 件、定義なども含めて 2 件）。

印の意味: ✓公理まで証明済み・ △証明あり（閉包未完）・ ※主張のみ。テーマごとの集計は閉包の状況。

前提をたどる証明が使う定理・定義（直接 2 件）

▸ を開くと、その項目の証明が使う前提が出ます。深い先は各項目のページでたどれます。

$K_5$ ・ $K_{3,3}$ の中の内素な道✓補題 6.2・Kuratowski の定理
細分された辺の一部を辺で置き換える✓補題 6.1・Kuratowski の定理

これを使っている定理証明で参照している 1 件

辺極大なら 3-連結✓補題 6.4・Kuratowski の定理