algorithm - 证明一个大小为 n 的团的任何最小顶点覆盖必须恰好有 n-1 个顶点

Question

如何证明一个大小为 n 的团的任何最小顶点覆盖必须恰好有 n-1 个顶点？谢谢

Answer 1

如果团中有两个顶点不在一个集合中，则它们之间的边不会被覆盖，因此任何覆盖必须至少有 n-1 个顶点。简单地说，任何 n-1 个顶点的子集都是一个覆盖。