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

マイナーの基本性質

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

$X$ が $Y$ のマイナーで、 $Y$ が $G$ のマイナーなら、 $X$ は $G$ のマイナーである。
$X$ が $G$ のマイナーであるためには、 $G$ のある部分グラフから辺の縮約を有限回くり返して $X$ と同型なグラフが得られることが必要十分である。
$G$ が $TX$ を含めば、 $X$ は $G$ のマイナーである。

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

閉包の状態

✓ 公理まで証明済み

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

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

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

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

全域木の存在✓系 4.5・道・閉路・木
- 木の同値な特徴づけ✓定理 4.4・道・閉路・木
  - 歩道から道を取り出す✓補題 2.5・道・閉路・木
    整列性公理 3.1・証明の技術
  - 相異なる 2 本の道は閉路を生む✓補題 4.3・道・閉路・木
  - 橋の特徴づけ✓命題 4.2・道・閉路・木
    歩道から道を取り出す✓補題 2.5・道・閉路・木（上で展開済み）
  - 森の辺の数と葉✓補題 2.2・グラフと行列式

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

平面性は部分グラフ・細分・縮約で保たれる✓命題 3.4・Kuratowski の定理
マイナーと位相的マイナー✓補題 3.6・Kuratowski の定理
3-連結グラフの凸な描画✓定理 5.6・Kuratowski の定理