グラフの部分点集合で、どの2点も隣接していないもの 点カバー グラフの部分点集合Sで、グラフのどの辺もSに含まれる点に接続している 二部グラフの場合、最小点カバーと、最大マッチングはサイズが同じ 一般のグラフで、最小点カバーと最大安定集合の頂点数を足すとグラフ自体の頂点数