정점은 그대로 둔다
정점 A,B,C가 있고 간선이 AB 하나뿐이면 여그래프에는 AC와 BC가 있다. 정점 A,B,C를 없애거나 새 정점을 만드는 연산이 아니다. 자기 고리도 새로 넣지 않는다.
두 번 취하면
서로 다른 정점 쌍마다 간선 유무를 두 번 뒤집으면 원래 상태가 된다. 따라서 단순 무향 그래프의 여그래프를 다시 취하면 원래 그래프를 얻는다.
완전 그래프와의 관계
원래 간선 집합과 여그래프의 간선 집합은 겹치지 않고 합치면 같은 정점들 위의 완전 그래프가 된다. 정점이 n개라면 두 그래프의 간선 수 합은 n(n−1)/2이다.
클리크와 독립 집합
원래 그래프에서 클리크를 이루던 정점들은 여그래프에서 독립 집합이 된다. 반대로 원래 독립 집합이던 정점들은 여그래프에서 클리크를 이룬다. 선택 집합 안의 모든 연결 유무가 뒤집히기 때문이다.
관련 문서
단순 그래프 / 무향 그래프 / 완전 그래프 / 클리크 / 독립 집합 (그래프 이론) / 정점 (그래프 이론) / 간선 (그래프 이론)