k-factor = 全域部分グラフであって，全頂点の次数が k 2 部グラフのマッチング 2 部マッチングのサイズ ＝ 頂点被覆のサイズ $|N(S)| \geq |S|$ for all $S \subseteq A$ stable matching は常に存在 一般グラフのマッチング G が 1-factor 持つ ⇔ $q(G-S) …