GATE CS 2026 Set 1 Q.47: Graph Theory

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

The degree of $v$ is at least $k + 1$

The vertex $v$ is on a path of length $k + 1$

The vertex $v$ is on a cycle of length $k + 1$

The vertex $v$ is a part of a clique of size $k$

Official answer and solution

Official answer: A
From: Official GATE 2026 answer key

Solution

Use the Buss kernelization observation: if $v \notin S$ , all neighbors of $v$ must belong to $S$ .

Option (A) is true: Suppose $\deg(v) \ge k + 1$ . If $v \notin S$ , then to cover every edge $(v, u)$ incident on $v$ , all $\deg(v) \ge k + 1$ neighbors of $v$ must be included in $S$ , which implies $|S| \ge k + 1$ , contradicting $|S| = k$ . Therefore, $v \in S$ is guaranteed.
Options (B), (C), and (D) are false: A path or cycle of length $k + 1$ has vertices that can be excluded from a minimum vertex cover (alternating vertices cover the path/cycle), and a clique of size $k$ only requires $k - 1$ of its $k$ vertices in any vertex cover, so one vertex of the clique can be excluded from $S$ .

Final answer

Option (A)

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2026 Computer Science and Information Technology - Session 1 (CS1)
Question: 47 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source