A vertex cover of an undirected graph G(V, E) is a subset V₁ ⊆ V vertices such…
2013
A vertex cover of an undirected graph G(V, E) is a subset V₁ ⊆ V vertices such that
Answer: C. If (u, v) ∈ E then u ∈ V₁ or v ∈ V₁ — A vertex cover is a subset of vertices where every edge in the graph has at least one endpoint included in that subset. This ensures all edges are covered by…
- A.
Each pair of vertices in V₁ is connected by an edge
- B.
If (u, v) ∈ E then u ∈ V₁ and v ∈ V₁
- C.
If (u, v) ∈ E then u ∈ V₁ or v ∈ V₁
- D.
All pairs of vertices in V₁ are not connected by an edge
Attempted by 53 students.
Show answer & explanation
Correct answer: C
A vertex cover is a subset of vertices where every edge in the graph has at least one endpoint included in that subset. This ensures all edges are covered by selecting vertices, distinguishing it from a clique where every pair of selected vertices must be connected.
A video solution is available for this question — log in and enroll to watch it.
Explore the full course: Mppsc Assistant Professor Computer Science Paper 2