König の定理と Dilworth の定理は互いに導ける

命題 5.2（「マッチング」§5）・ ✓公理まで証明済み

二部グラフ $G$ （二部分割 $(A,B)$ 、 $n$ 頂点）に対し、 $V(G)$ 上の半順序を「 $a<b\iff a\in A,\ b\in B,\ ab\in E(G)$ 」で定めると、鎖分割の最小個数は $n-\nu(G)$ 、幅は $n-\tau(G)$ である。したがって、この半順序集合に対する Dilworth の定理の主張は $\nu(G)=\tau(G)$ と同値である。
$n$ 元の有限半順序集合 $P=\{p_1,\dots,p_n\}$ に対し、頂点 $a_1,\dots,a_n,b_1,\dots,b_n$ をもち「 $a_ib_j$ が辺 $\iff p_i<p_j$ 」である二部グラフ $G_P$ を作る。このとき $P$ は $n-\nu(G_P)$ 個の鎖に分割でき、大きさ $n-\tau(G_P)$ 以上の反鎖をもつ。したがって、 $\nu(G_P)=\tau(G_P)$ から $P$ に対する Dilworth の定理が従う。

閉包の状態

✓ 公理まで証明済み

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

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

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

証明で明示的に参照している定理は、まだありません。