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.
Prove that any minimum vertex cover of a clique of size n must have exactly n-1 vertices [closed]
-
05-07-2023 - |
题
How to prove that any minimum vertex cover of a clique of size n must have exactly n-1 vertices? THx
解决方案
不隶属于 StackOverflow