Skip to content
GATEiit

GATE CSE 2026 Session 1 Q47: Condition forcing a vertex into every minimum vertex cover

Question

Let G(V,E)G(V, E) be a simple, undirected graph. A vertex cover of GG is a subset V′⊆VV' \subseteq V such that for every (u,v)∈E(u, v) \in E, u∈V′u \in V' or v∈V′v \in V'. Let the size of the smallest vertex cover in GG be kk. Let SS be any vertex cover of size kk.

For a vertex v∈Vv \in V, which of the following constraints will always ensure that v∈Sv \in S?

Try it: multiple select: one or more correct options

Select one or more options
Select all correct options. No negative marking, no partial marks.
Show answer and explanation

Answer: A (official GATE 2026 final answer key)

Concept used: If vv is left out, all its neighbours must be in the cover.

First step: If v∉Sv \notin S and deg⁡(v)≥k+1\deg(v) \ge k + 1, then SS contains at least k+1k + 1 neighbours, contradicting ∣S∣=k|S| = k.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2026 Session 1 CS question paper and final answer key, organised by IIT Guwahati. Question paper · Answer key

More Algorithms PYQs

PracticePractise Algorithms questions →Full paperAll GATE CSE 2026 Session 1 questions →