# UNDIRECTED HAMCYCLE to HAMPATH reduction

I'll define the problems

UHAMPATH

Input: A undirected graph G and 2 nodes, s and t

Question: Is there a hamiltonian path from s to t in G?

UHAMCYCLE

Input: A undirected graph G

Question: Is there a hamiltonian cycle in G?

$$UHAMCYCLE \leq_p UHAMPATH$$

my reduction is as followed $$(G) \to (G', s, t)$$

function(G)

for each e = (u, v) in E(G)
G' = G
add nodes u' and v' to G'
add edges (u', u) and (v, v')
s = u'
t = v'
if there is a hamilton path from s to t:
return (G', s, t)


Basically if there is a hamilton cycle in G then some edge in $$G$$ will form a hamilton path in $$G'$$.

An example to further illustrate the reduction:

 Graph G

(a) ---- --(d)
| \        |
|   \      |
|    \     |
|     \    |
|      \   |
|       \  |
|         \|      |
(b) ------ (c)

Has a clear Hamilton cycle (a, b, c, d).

If we choose edges (a, d)

Graph G'

(s)--(a) ---- --(d)
| \        |
|   \      |
|    \     |
|     \    |
|      \   |
|       \  |
|         \|
(b) ------ (c)--(t)


Doesn't have a hamilton path from s to t. However if you choose any other edge such as (a, d) then

(s)--(a) ---- --(d)--(t)
| \        |
|   \      |
|    \     |
|     \    |
|      \   |
|       \  |
|         \|
(b) ------ (c)


$$(s \to a \to b \to c \to d \to t)$$. Holds.

I'm confused whether or not I can use this line:

if there is a hamilton path from s to t:
return (G', s, t)


Checking to see if a graph has a hamilton path is NP complete but since we are looking to reduce it to it I think we can?