Q37

MCQ2 marks, −0.67

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)

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

(B)

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

(C)

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

(D)

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

Loading…