Let $G(V,E)$ be a simple, undirected graph. A vertex cover of $G$ is a subset $V^{\prime} \subseteq V$ such that for every $(u,v) \in E$, $u \in V^{\prime}$ or $v \in V^{\prime}$. 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 vertex cover $S$ must contain at least one endpoint of every edge in $E$.

Consider the constraint "The degree of $v$ is at least $k+1$" (Option A):

• Suppose $v \notin S$.

• Then for every neighbor $u$ of $v$, the edge $(u,v)$ must be covered by $S$.

• Since $v \notin S$, every neighbor of $v$ must belong to $S$.

• Because the degree of $v$ is at least $k+1$, $v$ has at least $k+1$ distinct neighbors.

• This implies $|S| \ge k+1$, which directly contradicts the fact that the size of $S$ is $k$.

• Therefore, it is impossible for $v \notin S$, meaning $v \in S$ must always hold.

For the other options:

• (B) $v$ being on a path of length $k+1$ does not guarantee $v \in S$ (for example, in a simple path, vertex covers can alternate vertices without requiring a specific vertex).

• (C) $v$ being on a cycle of length $k+1$ similarly does not force $v$ to be in every minimum vertex cover.

• (D) In a clique of size $k$, any $k-1$ vertices cover all internal clique edges, so any specific vertex can be omitted.

Thus, only (A) ensures $v \in S$.