간선을 빠짐없이 덮는다
A—B—C라는 경로에서는 {B}가 두 간선을 모두 덮는다. {A,C}도 덮개지만 원소가 더 많다. 고른 정점이 모든 정점에 닿아야 한다는 지배 집합의 조건과는 다르다.
독립 집합과 연결
정점 덮개 C 밖의 정점끼리 간선이 있다면 그 간선은 C에 닿지 않아 덮이지 않는다. 따라서 V∖C는 독립 집합이다. 반대로 독립 집합의 나머지 정점들은 덮개를 이룬다.
최소와 극소
정점을 더 빼면 덮개가 아니게 되는 경우는 극소 덮개다. 모든 덮개 가운데 크기가 가장 작으면 최소 덮개다. 더 줄일 수 없다는 것과 그래프 전체에서 가장 작다는 것은 구별한다.
매칭으로 얻는 하한
서로 끝점을 공유하지 않는 간선 k개가 있으면 그 각각을 덮는 데 서로 다른 정점이 적어도 k개 필요하다. 따라서 어떤 매칭의 간선 수도 최소 정점 덮개의 크기에 대한 하한이 된다.
관련 문서
독립 집합 (그래프 이론) / 매칭 (그래프 이론) / 정점 (그래프 이론) / 간선 (그래프 이론) / 경로 그래프 / 부분집합 / 여집합