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$

2 Answers 2

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$
6
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ so it looks like an hourglass with a vertex in the center $\endgroup$
    – user124978
    Feb 3, 2014 at 23:49
  • $\begingroup$ Right. If you want to you can add a few cycles to make a flower :) $\endgroup$
    – Pifagor
    Feb 3, 2014 at 23:58

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.