NP-completness Consider the following problems A and B: A = Vertex-Cover. B = { | G is an undirected graph with an even number of vertices, and there exists a vertex cover with exactly half the vertices}. Show that B is NP-complete by showing that: (a) B NP. That is, show that given a solution, this solution can be veri ed in polynomial time. (b) B is NP-hard, by showing that A p B. Hint: Remember that an instance for A (the Vertex-Cover problem) is given as . For the mapping to B, consider three cases for k with respect to |V|/2.