2
$\begingroup$

i need to give an example of a connected graph with at least 5 vertices that has as an Eulerian circuit, but no Hamiltonian cycle?

$\endgroup$
6
$\begingroup$

Any "figure eight" graph will do. That is make one vertex the "center" and make to non-intersecting cycles containing it.

$\endgroup$
  • $\begingroup$ so it looks like an hourglass with a vertex in the center $\endgroup$ – user124978 Feb 3 '14 at 23:49
  • $\begingroup$ Right. If you want to you can add a few cycles to make a flower :) $\endgroup$ – Pifagor Feb 3 '14 at 23:58
  • $\begingroup$ great thanks :) $\endgroup$ – user124978 Feb 4 '14 at 0:36
7
$\begingroup$

The complete bipartite graph $K_{2,4}$ has an Eulerian circuit, but is non-Hamiltonian (in fact, it doesn't even contain a Hamiltonian path).

$K_{2,4}$

Any Hamiltonian path would alternate colors (and there's not enough blue vertices). Since every vertex has even degree, the graph has an Eulerian circuit.

$\endgroup$

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.