1
$\begingroup$

I know that if a graph is Eulerian then there exists an Eulerian cycle that contains all edges of the graph. I also know that if a graph is Hamiltonian then there exists a Hamiltonian cycle that contains all vertices of the graph.

It is easy for me to observe that a Hamiltonian graph may not be Eulerian (because may exist edges not contained in the Hamiltonian cycle). However, I'm a bit confused about the other direction. Is all Eulerian graphs also Hamiltonian?

$\endgroup$
7
$\begingroup$

It is not the case that every Eulerian graph is also Hamiltonian. It is required that a Hamiltonian cycle visits each vertex of the graph exactly once and that an Eulerian circuit traverses each edge exactly once without regard to how many times a given vertex is visited. Take as an example the following graph:

enter image description here

It's easy to find an Eulerian circuit, but there is no Hamiltonian cycle because the center vertex is the only way one can get from the left triangle to the right.

$\endgroup$
  • $\begingroup$ Thank you. The "...without regard to how many times a given vertex is visited" was missing for me. $\endgroup$ – Pedro Alves Nov 28 '17 at 17:15
3
$\begingroup$

Counterexample: the complete bipartite graph $K_{2,4}$ is Eulerian but not Hamiltonian.

$\endgroup$
  • $\begingroup$ Can you clarify this? I don't see how to draw an Eulerian cycle (no repeated edges or vertex) on $K_{2,4}$. $\endgroup$ – Pedro Alves Nov 28 '17 at 17:05
  • 1
    $\begingroup$ @PedroAlves, $K_{2n,2m}$ has no odd vertices, so it has an Eulerian cycle. The statement in the question ("that contains all edges of the graph") is the correct definition. $\endgroup$ – Peter Taylor Nov 29 '17 at 12:55

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.