Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
add comment

1 Answer

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|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
add comment

Your Answer

 
discard

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.