ยง Remembering Eulerian and Hamiltonian cycles

I used to keep forgetting the difference. Here's how I remember it now. We know that an euler tour always exists for a tree. Indeed, it's a handy data structure that can be used to convet LCA (lowest common ancestor) into RMQ(range minimum query). So, the "Euler tour" must exist for a tree. See that when we perform a tour on the tree, we definitely walk a vertex twice (once when entering, once when exiting). It seems like we walk the (undirected) edges twice as well. However, if we consider the edges as directed edges, then we're only walking the edges once.
  • So an euler tour must correspond to a tour where we walk over each edgeexactly once.
  • A hamiltonian tour must (by complementarity) correspond to a tour where weover each vertex exactly once.