Let πΊ(π,πΈ) be a simple, undirected graph. A vertex cover of πΊ is a subsetβ¦
PYQ GATE 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 85 students.
Sign up free to check your answer
Sign up freeLoading lessonβ¦

