数学 › グラフ理論 › 道・閉路・木

Bondy–Chvátal の閉包定理

定理 6.9（「道・閉路・木」§6）・ ✓公理まで証明済み

$n\ge3$ 頂点のグラフ $G$ について、次が成り立つ。

$\operatorname{cl}(G)$ は、辺を足す順序によらずに定まる。
$G$ が Hamilton 閉路をもつことと、 $\operatorname{cl}(G)$ が Hamilton 閉路をもつことは同値である。
とくに $\operatorname{cl}(G)=K_n$ ならば、 $G$ は Hamilton 閉路をもつ。

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

閉包の状態

✓ 公理まで証明済み

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

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

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

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

完全帰納法✓定理 4.3・証明の技術
- 数学的帰納法の原理✓定理 3.2・証明の技術
  - 背理法の正当性✓命題 6.2・証明の技術
  - 整列性公理 3.1・証明の技術
辺を 1 本足しても Hamilton 性は変わらない✓補題 6.7・道・閉路・木
- 端点の次数の和が大きい Hamilton 道は閉じられる✓補題 6.4・道・閉路・木

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

Chvátal の次数列条件✓系 6.10・道・閉路・木

関連するノック 1 問

グラフ理論第 8 問