1
$\begingroup$

Let $G$ be a graph in which every vertex has odd degree. Show that every edge of $G$ lies on an even number of Hamilton cycles.

$\endgroup$
8
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.