Vertex cover problem is NP complete
A vertex cover of an undirected graph G=(V,E) is a sub set 𝑉^′⊆𝑉 such that if (𝑢,𝑣)∈𝐸 , then 𝑢∈𝑉^′ or 𝑣∈𝑉^′, or both.
That is, each vertex “covers” its incident edges, and a vertex cover for G is a set of vertices that covers all the edges in E.
The size of a vertex cover is the number of vertices in it.
Is the graph contain a vertex cover of size k ?