GATE 2026 CS1 Q.47: solution and answer

GATE 2026 · CS1Q.47 · 2 marks · MSQ

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$ ?

(A)
The degree of $v$ is at least $k + 1$
(B)
The vertex $v$ is on a path of length $k + 1$
(C)
The vertex $v$ is on a cycle of length $k + 1$
(D)
The vertex $v$ is a part of a clique of size $k$

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

Only option A always ensures $v \in S$ , so the answer is (A).

Official answer: ASource: Official answer key, GATE 2026 CS1 (IIT Guwahati)

Let $S$ be a vertex cover of the smallest size $k$ . If a vertex $v \in / S$ , every edge $(v, u)$ must be covered by $u$ , so all neighbours of $v$ lie in $S$ .
(A) Suppose $de g (v) \geq k + 1$ and $v \in / S$ . Then $S$ contains at least $k + 1$ distinct neighbours of $v$ , so $∣ S ∣ \geq k + 1 > k$ , a contradiction. Hence $v \in S$ for every minimum cover $S$ . A always ensures $v \in S$ .
(B) Take the path $a - b - c$ . The smallest cover is ${b}$ , so $k = 1$ , and the path has length $2 = k + 1$ . The end vertex $a$ is on this path but $a \in / S$ . B fails.
(C) Take the triangle $K_{3}$ , a cycle of length $3$ . Its smallest cover has size $k = 2$ , so the cycle has length $k + 1 = 3$ . The cover ${a, b}$ has size $2$ and omits $c$ , which lies on the cycle. C fails.
(D) Take $K_{3}$ with vertices $a, b, c$ . Again $k = 2$ . The vertex $c$ is part of the clique ${a, c}$ of size $2 = k$ . The minimum cover ${a, b}$ omits $c$ . D fails.
Only (A) is guaranteed, so the answer is A.

KEY IDEA

A vertex left out of a cover forces all its neighbours into it, so a vertex with more than $k$ neighbours cannot be left out of a cover of size $k$ .

WATCH OUT FOR

Assuming that lying on a long path or cycle, or inside a clique, forces membership. In a cycle or clique, a cover can skip any one vertex, so the structure alone does not force $v$ into $S$ .

From the GATE 2026 CS1 paper. Every question of this paper · Download the full paper · All 14 Graph theory questions, with notes

GATE 2026 CS1 Q.47: solution and answer

Answer and solution

More Graph theory questions