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

Let G(V,E) be a simple, undirected graph. A vertex cover of G is a subset V' V such that for every (u,v) E, u V' or v 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 V, which of the following constraints will always ensure that v S?

Topic-wise GATE CS PYQs with verified steps