GATE CS 2026 Set 1 Q37 — Graphs: Connectivity, Matching, Colouring

To find which constraint always ensures that $v \in S$, let us analyze each option:

• Option A: Suppose $v \notin S$. To cover all the edges incident on $v$, every neighbor of $v$ must be included in the vertex cover $S$. Since the degree of $v$ is at least $k+1$, we must have at least $k+1$ neighbors of $v$ in $S$. This implies $|S| \ge k+1$, which contradicts the given fact that the size of $S$ is $k$. Thus, $v$ must belong to $S$.
• Option B: Consider a path $v_0 - v_1 - v_2$ of length 2. The minimum vertex cover size is $k = 1$, and $S = \{v_1\}$. The vertex $v_0$ lies on this path of length $k+1 = 2$, but $v_0 \notin S$.
• Option C: Consider a cycle $C_3$ (triangle $v_0 - v_1 - v_2 - v_0$). The minimum vertex cover size is $k = 2$. We can choose $S = \{v_1, v_2\}$. The vertex $v_0$ is on a cycle of length $k+1 = 3$, but $v_0 \notin S$.
• Option D: Consider $G = K_2$ (an edge $u - v$), which is a clique of size $2$. Here, the minimum vertex cover size is $k = 1$. We can choose $S = \{u\}$. The vertex $v$ is part of a clique of size $2$ (which is $k+1$ here, but even if we consider a clique of size $k=1$, it is trivial), and $v \notin S$.