1
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .