[NP-completeness]

Consider the following problems A and B:

A = Vertex-Cover.

B = {?G? | 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 verified 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 ?G,k?. For the mapping to B, consider three cases for k with respect to