Let πΊ(π,πΈ) be a simple, undirected graph. A vertex cover of πΊ is a subsetβ¦
GATE Β· 2026 Β· CS Β· Set 1 Β· Computer Science & IT
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 66 students.
Sign up free to check your answer
Sign up freeLoading lessonβ¦