Is knowing information about Euler paths and Euler tours about a graph $G$ the same as knowing information about Hamilton paths and cycles of the graph $H$ obtained from $G$ such that vertices of $H$ are edges of $G$ and two vertices of $H$ are joined by an edge if the corresponding edges are adjacent?


Not entirely; the relationship is only one-way.

An Eulerian walk in $G$ gives us a Hamiltonian path in $H$ (the line graph of $G$) and an Eulerian tour in $G$ gives us a Hamiltonian cycle in $H$. This is because consecutive edges $uv, vw$ in the Eulerian walk in $G$ correspond to adjacent vertices in $H$.

However, other Hamiltonian paths/cycles in $H$ may not correspond to Eulerian walks/tours in $G$. For example, if $G = K_4$ (with vertices $1,2,3,4$ and edges $12, 13, 24, 23, 24, 34$) then in $H$, we have a Hamiltonian cycle $12, 13, 14, 34, 24, 23$ which does not correspond to an Eulerian tour of $G$ (and in fact such an Eulerian tour does not exist).

The difference is that a path in $H$ is a sequence of edges of $G$ in which any two consecutive edges share a vertex. However, a walk in $G$ is more structured: the second endpoint of one edge must be the first endpoint of the next. Going from $12$ to $13$ to $14$ in $H$ (a valid part of a Hamiltonian cycle) cannot be made to follow this rule in $G$: if $12$ and $13$ share the vertex $1$, the next edge should include vertex $3$, not vertex $1$ again.


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.