此以下属性来自Wiki顶点覆盖:当且仅当其补集是独立集合时,一组顶点才是顶点覆盖。
我想知道我们如何证明这是真的?如果可以通过矛盾证明这一点很好,但所有其他证明方式也应受到赞赏。
谢谢!
一些提示:
如果我是一个独立集合,并且V-我不是顶点覆盖,那么在V-I中存在一个端点都没有端点的边。因此...?
如果V-I是顶点覆盖,则选择任意边。如果两个端点都在I中,则...?
祝你好运!