G is a directed graph and s and t are 2 vertices in G.
$2HC = \{(G, s, t): \; G $ has at least 2 edge-disjoint Hamilton paths $\}$
Prove that $2HC$ is NP-Complete.
I'm trying to reduce UHAMPATH to $2HC$.
G is an undirected graph.
$UHAMPATH = \{(G, s, t): \; G $ has a Hamilton path from s to t $\}$
Given an instance G(V, E) of UHAMPATH, construct a directed graph G' from G as follows:
1) For every edge (u, v) where u, v $\in$ V - {s, t}, add an edge (v, u)
2) for every edge (s, v) where v $\neq s, t$ add an edge (v, t)
3) for every edge (v, t) where v $\neq s, t$ add an edge (s, v)
The idea is that a HAM-PATH $s-v_1-...-v_n-t$ exists iff $s-v_n-...-v_1-t$ exists.
So, we have 2 edge-disjoint Hamilton paths.
This should mean that G has a HAMPATH $\Leftarrow\Rightarrow$ G' has at least 2 edge-disjoint HAMPATH
I'd like to know if the reduction works?