algorithmnp-completecliquevertex-cover

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

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

Solution

  • 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.