Let πΊ(π,πΈ) be a simple, undirected graph. A vertex cover of πΊ is a subsetβ¦
2026
Let πΊ(π,πΈ) be a simple, undirected graph. A vertex cover of πΊ is a subset Vβ²βπ such that for every (π’,π£)βπΈ, π’βπβ²or π£βπβ². Let the size of the smallest vertex cover in πΊ be π. Let π be any vertex cover of size π.
For a vertex π£βπ, which of the following constraints will always ensure that π£βπ ?
- A.
The degree of π£ is at least π+1
- B.
The vertex π£ is on a path of length π+1
- C.
The vertex π£ is on a cycle of length π+1
- D.
The vertex π£ is a part of a clique of size π
Attempted by 11 students.
Show answer & explanation
Correct answer: A
A vertex cover S of size k covers all edges in G. If a vertex v is not in S, then all its neighbors must be in S to cover the edges incident to v. This implies that |S| >= deg(v). Since |S| = k, we must have deg(v) <= k for v to potentially be excluded from S. Conversely, if deg(v) > k (or equivalently deg(v) >= k+1), it is impossible for v to be excluded from S because that would require more than k vertices in the cover. Therefore, any vertex with degree greater than k must be included in every minimum vertex cover of size k.