Question

Let 𝐺(𝑉, 𝐸) be a simple, undirected graph. A vertex cover of 𝐺 is a subset
𝑉′ ⊆𝑉 such that for every (𝑢, 𝑣) ∈𝐸, 𝑢∈𝑉′or 𝑣∈𝑉′. Let the size of the smallest
vertex cover in 𝐺 be 𝑘. Let 𝑆 be any vertex cover of size 𝑘.
For a vertex 𝑣∈𝑉, which of the following constraints will always ensure that
𝑣∈𝑆 ?

• A. The degree of 𝑣 is at least 𝑘+ 1
• B. The vertex 𝑣 is on a path of length 𝑘+ 1
• C. The vertex 𝑣 is on a cycle of length 𝑘+ 1
• D. The vertex 𝑣 is a part of a clique of size 𝑘

Hint:

If a vertex v is excluded from a size-k minimum vertex cover, every neighbour of v must be included instead to cover v's edges. Compare the number of neighbours needed against the budget k to see which condition creates an impossible contradiction.

Answer 1

The Correct Option is A

We are given a simple undirected graph \(G(V, E)\). A vertex cover \(V' \subseteq V\) is a set of vertices such that every edge has at least one endpoint in \(V'\). Let \(k\) be the size of the minimum vertex cover, and let \(S\) be any minimum vertex cover of size \(k\). We must find which condition on a vertex \(v\) guarantees \(v \in S\) for every choice of minimum vertex cover \(S\).

Step 1: Test option (A) - degree of v is at least k+1.

Suppose, for contradiction, that \(v \notin S\) even though \(\deg(v) \ge k+1\). Since \(S\) is a vertex cover, every edge incident on \(v\) must still be covered. Because \(v \notin S\), for every edge \((v, u) \in E\), the other endpoint \(u\) must belong to \(S\).

Since \(\deg(v) \ge k+1\), vertex \(v\) has at least \(k+1\) distinct neighbours, all of which must lie in \(S\). This forces \[|S| \ge k+1\] which contradicts \(|S| = k\). So the assumption \(v \notin S\) is false, meaning \(v \in S\) always holds. Option (A) is correct.

Step 2: Rule out option (B) - v lies on a path of length k+1.

Take \(G\) to be the path \(a - b - c\) (2 edges). The minimum vertex cover is \(S = \{b\}\), so \(k = 1\). This path has length \(2 = k+1\), and vertex \(a\) lies on it, yet \(a \notin S\). So the path condition does not guarantee membership. Option (B) fails.

Step 3: Rule out option (C) - v lies on a cycle of length k+1.

Take \(G\) to be a triangle on vertices \(a, b, c\). The minimum vertex cover has size \(k = 2\), for example \(S = \{a, b\}\). The triangle is a cycle of length \(3 = k+1\), and vertex \(c\) lies on it but \(c \notin S\). Option (C) fails.

Step 4: Rule out option (D) - v is part of a clique of size k.

Take \(G = K_{k+1}\), the complete graph on \(k+1\) vertices. Its minimum vertex cover has size \(k\), obtained by dropping exactly one vertex (its edges are all covered by the remaining \(k\) vertices). Any \(k\)-subset of \(K_{k+1}\) forms a clique of size \(k\), so the dropped vertex still belongs to many size-\(k\) cliques, yet it is excluded from \(S\). Option (D) fails.

Step 5: Conclusion.

Only the degree condition in option (A) forces \(v\) into every minimum vertex cover.

\[\boxed{\text{Correct answer: (A) degree of } v \text{ is at least } k+1}\]