The GATE Grind

GATE 2026 CS (CS1) – Question 47

Algorithms · Asymptotic Analysis and Time/Space Complexity · 2 marks · Multiple choice

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

  1. The degree of $v$ is at least $k + 1$
  2. The vertex $v$ is on a path of length $k + 1$
  3. The vertex $v$ is on a cycle of length $k + 1$
  4. The vertex $v$ is a part of a clique of size $k$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) The degree of $v$ is at least $k + 1$

Explanation

Let $S$ be a vertex cover of size $k$. By definition, $S$ covers all edges in $E$.
- Suppose for contradiction that $v \notin S$.
- Then for every neighbor $u$ of $v$, the edge $(v, u)$ MUST be covered by $S$. Since $v \notin S$, this requires $u \in S$ for every neighbor $u$ of $v$.
- Therefore, all neighbors of $v$ must be in $S$, which implies $|S| \ge \text{degree}(v)$.
- If $\text{degree}(v) \ge k + 1$, then $|S| \ge k + 1$, which directly contradicts the fact that $|S| = k$.
- Hence, if $\text{degree}(v) \ge k + 1$, it is mathematically impossible for $v$ to be excluded from $S$; $v$ MUST belong to every vertex cover of size $k$.

Therefore, option (A) is correct.