頂点被覆・独立集合・辺被覆

定義 2.2（「マッチング」§2）

$K\subseteq V(G)$ が頂点被覆であるとは、どの辺も $K$ の頂点を端点にもつことをいう。最小の大きさを被覆数 $\tau(G)$ という。
$I\subseteq V(G)$ が独立集合であるとは、 $I$ のどの 2 頂点も隣接しないことをいう。最大の大きさを独立数 $\alpha(G)$ という。
$L\subseteq E(G)$ が辺被覆であるとは、どの頂点も $L$ のある辺の端点であることをいう。最小の大きさを辺被覆数 $\rho(G)$ という（孤立点のないグラフでだけ定義される）。
$S\subseteq V(G)$ の近傍を $N(S)=\bigcup_{v\in S}N(v)$ と書く。

閉包の状態

定義

定義は閉包の起点です（証明を要しません）。

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

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