===========================================================================
CSC 363H              Tutorial Exercises for Week 10            Summer 2006
===========================================================================

Show that HAM-CYCLE (defined below) is NP-complete.  You're allowed to
assume that HAMPATH is NP-complete (yes, that's a barely concealed hint) --
recall that HAMPATH = { <G,s,t> : G is a graph that contains a Hamiltonian
path from s to t }.

    HAM-CYCLE = { <G> : G is a graph that contains a Hamiltonian cycle }

A Hamiltonian cycle in a graph G is a simple cycle that includes every
vertex of G, i.e., a list of the vertices v_1, v_2, ..., v_n such that
every vertex occurs exactly once in the list and G contains all of the
edges (v1,v2), (v2,v3), ..., (v_{n-1}, v_n), (v_n,v_1).