Show that the following problems (defined in the text) are in NP: vertex-cover (VC) directed Hamiltonian path (DHP) 3-colouring (3C) and show that the transformations: 3SAT cc VC (theorem 8.3) VC cc...

1. 
   

   
   Show that the following problems (defined in the text) are in
   
   NP:
   
   

   
   

vertex-cover

(VC)

directed Hamiltonian path

(DHP)

3-colouring (3C)

and show that the transformations:

3SAT



cc

VC



(theorem 8.3)

VC

cc

DHP

(theorem 8.6) and

3SAT

cc 3C (theorem 8.10) are indeed polynomial.