Proof that Hamiltonian cycle/circuit with a specified edge is NP-complete I'm a little stuck on this question, any help would be appreciated!

Given that the Hamiltonian Path (HP) and the Hamiltonian Circuit/Cycles (HC) problems are known to be NP-complete, show that HCE is NP-complete.

HCE: Given an undirected graph G and an edge e of G, does G have a Hamiltonian circuit/cycle that uses e?

I've tried to approach this by showing that HC $\leq$ HCE, but I'm wondering if my approach is too convoluted.

EDIT:

I think I have a solution.
Consider a graph $G=(V,E)$ where $V$ is the set of vertices in $G$,
and $E$ is the set of edges in $G$. Let $f(G)=G'=(V',E')$ where

\begin{alignat*}{1}
V'= &amp; V\cup\{v_{\alpha},v_{\beta},v_{\gamma}\},v_{\alpha},v_{\beta},v_{\gamma}\notin V\\
E'= &amp; E\cup\{(v_{\alpha},v_{\beta}),(v_{\beta},v_{\gamma})\}\cup\{\bigcup_{i\in\{\alpha,\gamma\},v\in V}(v,v_{i})\}
\end{alignat*}

Let the edge $e=(v_{\alpha},v_{\beta})$.

$G'$is the graph $G$ with three additional vertices. $v_{\alpha}$
and $v_{\gamma}$ are connected to all the vertices in $G$ and $v_{\beta}$.
$v_{\beta}$ has a degree of 2, and is only connected to $v_{\alpha}$and
$v_{\gamma}$. $f$ can be computed in p-time.

Consider some $G$ that has a HP along vertices $v_{1},v_{2},...,v_{n}$.
Then $G'$ will also have a path $v_{1},v_{2},...,v_{n}$ with each
vertex only appearing once in the path. In order to turn this path
into a HC, the three additional vertices will have to be included.
In order to do so, the path has to be extended in either $v_{n},v_{\alpha},v_{\beta},v_{\gamma},v_{1}$
or $v_{n},v_{\gamma},v_{\beta},v_{\alpha},v_{1}$. $G'$ thus have
a HC that will always include the edge $e$.

$\therefore$ G $\in$ HP $\implies$$f(G)=G'\in$ HCE

Consider some $G'$ with a HCE along some path $v_{1},v_{2},...,v_{n},v_{\alpha},v_{\beta},v_{\gamma},v_{1}$.
Since $G$ has vertices $V=V'\backslash{v_{\alpha},v_{\beta},v_{\gamma}}$,
$G$ has a HP along vertices $v_{1},v_{2},...,v_{n}$. 

$\therefore$ $G'\in$ HCE $\implies G\in$ HP

And thus $G\in$ HP iff $f(G)=G'\in$ HCE. Since $f$ can run in p-time,
HP $\leq$ HCE.

$\therefore$ HCE is NP-complete.
Given: a graph $G$, an edge $e$, and a length $k$.

Optimization problem output: a cycle of length $k$, containing $e$ (or none, if there is none).

Decision problem output: "yes" if such a cycle exists, "no" otherwise.

Now, it is obviously in NP, as you can simply check any answer to the optimization problem; see if it is a cycle, see if the cycle contains $e$, and check that the length of the cycle is $k$.

There are two easy ways to prove it is NP-hard. Imagine you had a magic algorithm, ${\rm M{\small AGIC}}(G,e,k)$, that can answer this for you.

Method 1 hint: In the k-SAT to DHC  (directed Hamiltonian cycle) reduction, aren't there some edges that must occur? (and don't these carry over to UHC (undirected Hamiltonian cycle)?)

More hints (mouseover):


   The reduction from k-SAT to DHC (directed Hamiltonian cycle) involved a root node, and a sink node. The sink node has an edge to the root node; and it is the only incoming edge to the root node; hence, the sink-root edge must be used in the DHC.


 Furthermore, in the reduction from DHC to UHC, each node gets split into 3 nodes, and the middle one is connected to the two outer ones with a single edge. Well, as a general rule, any degree-2 nodes make it easy to solve this problem (because the cycle must pass through it).


Method 2 hint: What happens if you pick a node. The Hamiltonian Cycle must pass through one of its edges. How many edges can a node have?

More hints (mouseover):


   Maybe you can solve a regular UHC with some calls to ${\rm M{\small AGIC}}(G,e,k)$.