Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 6 down vote accepted

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

share|cite|improve this answer
There's two mistakes of notation. First, in the second paragraph is {vn,vk} instead of {vn,nk}. Second, {vn,u} is an edge of G instead {vn,u} is an edge of V. – Andrés Felipe Téllez Crespo Jan 27 '13 at 22:42
Thank you for your help – Andrés Felipe Téllez Crespo Jan 27 '13 at 22:42
@Andrés: You’re welcome, and thanks for catching the typos. – Brian M. Scott Jan 27 '13 at 22:44

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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