In the decision version of the minimum vertex cover problem in a bipartite…
2025
In the decision version of the minimum vertex cover problem in a bipartite graph, if the answer is "No", what serves as a valid No certificate?
- A.
A matching of size K + 1
- B.
A vertex cover of size K - 1
- C.
An edge not included in the cover
- D.
A subgraph with no matchings
Attempted by 28 students.
Show answer & explanation
Correct answer: A
According to Konig's Theorem, the size of a minimum vertex cover equals the size of a maximum matching in any bipartite graph. If the decision problem answer is "No", then the minimum vertex cover must be larger than K. Consequently, the maximum matching size must also exceed K. A valid certificate for this "No" answer is a specific matching of size K+1, which proves the minimum vertex cover cannot be as small as K.