Множество вершин является покрытием вершин тогда и только тогда, когда его дополнение является независимым множеством

Question

Это следующее свойство из покрытия вершин вики: набор вершин является покрытием вершин тогда и только тогда, когда его дополнение является независимым набором.

Мне было интересно, как мы можем доказать, что это правда? Было бы здорово, если бы это можно было доказать противоречием, но все другие способы доказать также приветствуются.

спасибо!

Answer 1

Некоторые подсказки:

• Если I - независимое множество, а V - I - не покрытие вершины, то есть ребро, где ни одна конечная точка не находится в V - I. Поэтому. ..?

• Если V - I - вершинное покрытие, выберите любой край. Если обе конечные точки были в I, то ...?

Удачи!