Edges on an even number of Hamilton cycles

Solution 1:

Let $e=\{u,v_0\}$ be an edge in the graph $G$, whose vertices all have odd degree. Let $P$ be the set of Hamilton paths that begin $u,e,v_0$; $P$ will be the vertex set of a new graph $H$. Suppose that $p\in P$ is $u,e,v_0,e_0,v_1,\dots,e_{n-1},v_n$. If $\{v_n,v_k\}$ is an edge for some $k<n-1$ we can remove the edge $e_k=\{v_k,v_{k+1}\}$ and add the edge $e'=\{v_n,v_k\}$ to get $$q=u,e,v,e_0,v_1,\dots,v_k,e',v_n,e_{n-1},v_{n-1},\dots,v_{k+1}\;,$$ another path in $P$. Note that $p$ can be obtained from $q$ by a similar operation. If $p_1,p_2\in P$, $\{p_1,p_2\}$ is an edge of $H$ iff each can be obtained from the other as $q$ was obtained from $p$.

Fix $p\in P$ as above. Then $\deg_H(p)$ is just the number of edges $\{v_n,v_k\}$ with $k<n-1$. This accounts for every edge of $G$ incident at $v_n$ except $e_{n-1}=\{v_{n-1},v_n\}$ and possibly $\{v_n,u\}$. If $\{v_n,u\}$ is an edge of $G$, then $p$ is part of a Hamilton cycle through $e$, and $\deg_H(p)=\deg_G(v_n)-2$, which is odd; otherwise, $p$ is not part of a Hamilton cycle through $e$, and $\deg_H(p)=\deg_G(v_n)-1$, which is even. $H$ must have an even number of odd vertices, so $G$ must have an even number of Hamilton cycles through the edge $e$.