HAMPATH

HAMCYCLE

I wish to show HAMCYCLE is NP-hard

I’ll show this by doing $ HAMPATH \leq_p HAMCYCLE$ since HAMPATH is known to be NP-COMPLETE

Reduction is as follows

$ (G, s, t) \to (G’, s’)$

where $ s’ = s$ and for $ G’$ I will add one edge from $ t$ to $ s’$

This is polynomial time because we are adding only an edge

if $ (G, s, t) \in HAMPATH$ , then we know there is a hamilton path from s to t, our graph G’ will be $ (s’, \dots, t)$ but since we added a edge from $ t$ to $ s’$ then

$ (s’, \dots, t, s’)$ , a cycle, thus $ (G’,s’) \in HAMCYCLE$

Now doing the converse, if $ (G’, s’) \in HAMCYCLE$ then there exist a hamilton cycle from $ (s’, …, s’)$ that visits every node and comes back to s’ meaning there is a node $ t$ right before $ s$ to make this a hamilton path, thus $ (G, s, t) \in HAMPATH$

Above is my entire attempt. I was wondering if I could call on $ t$ in my reduction since its not used as a input in HAMCYCLE ?