Prove that any minimum vertex cover of a clique of size n must have exactly n-1 vertices [closed]

Question

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

This question does not appear to be about programming within the scope defined in the help center.

Closed 9 years ago.

Improve this question

How to prove that any minimum vertex cover of a clique of size n must have exactly n-1 vertices? THx

Answer 1

If there's two vertices from the clique not in a set, then the edge between them isn't covered, so any cover must have at least n-1 vertices. Any subset of n-1 vertices is a cover, trivially.