graph - 一个顶点集是一个顶点覆盖当且仅当它的补集是一个独立集

Question

以下属性来自 wiki 顶点覆盖：当且仅当其补集是独立集时，一组顶点才是顶点覆盖。

我想知道我们如何证明这是真的？如果它可以通过矛盾来证明，那就太好了，但所有其他证明方式也受到赞赏。

谢谢你！

Answer 1

一些提示：

• 如果 I 是一个独立集并且 V - I 不是顶点覆盖，那么有一条边，两个端点都不在 V - I 中。因此...？

• 如果 V - I 是顶点覆盖，则选择任何边。如果两个端点都在 I 中，那么...？

祝你好运！