SI333 Quiz 3 (Corrected Version!)

The HAM-PATH problem is the following: Given an undirected graph G, is there a path in G that visits all vertices exactly once.
  1. Give a sketch of a proof that HAM-PATH is in NP.
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
  2. Here is a reduction of HAM-CYCLE to HAM-PATH. [HAM-CYCLE asks if there is a cycle, i.e. a loop, that visits all the vertices exactly once.]
    Input: G a graph
    Output: G' a graph such that HAM-CYCLE for G is equivalent to HAM-PATH for G'
    Create a new graph G' by starting with G and doing the following:
    1. choose a vertex from G, call it u
    2. add a new vertex u', along with edges from u' to each of the neighbors of u
    3. add new vertices v and v' with edges (u,v) and (u',v')
    Prove that HAM-CYCLE for G is equivalent to HAM-PATH for G', i.e. that my reduction is correct.