Proof that Hamiltonian cycle/circuit with a specified edge 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)$.