Let G(V, E) be a simple, undirected graph. A vertex cover of G is a subset \(V' \subseteq V\) such that for every \((u, v) \in E\), \(u \in V'\) or \(v \in V'\). Let the size of the smallest vertex cover in G be k. Let S be any vertex cover of size k.
For a vertex \(v \in V\), which of the following constraints will always ensure that \(v \in S\) ?
GATE CS - 2026,
Answer: A
The constraint that always forces v into S is The degree of v is at least k + 1.
If v were not in S, every edge at v would have to be covered by its other endpoint, so all of v's at least k + 1 neighbours would be in S. That makes S larger than k, a contradiction. So v must be in every minimum vertex cover.
The other conditions do not force it. In the path a-b-c the minimum cover is {b}, so k = 1, and a lies on a path of length 2 = k + 1 without being in the cover. In a triangle k = 2, every vertex lies on a cycle of length 3 = k + 1 and in a clique of size 2 = k, yet any one vertex can be left out of a minimum cover.
Please log in or register to report this question.