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?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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).
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.
answered Feb 3, 2014 at 23:54
$\begingroup$
$\endgroup$
2
Any "figure eight" graph will do. That is make one vertex the "center" and make to non-intersecting cycles containing it.
-
$\begingroup$ so it looks like an hourglass with a vertex in the center $\endgroup$ Feb 3, 2014 at 23:49
-
$\begingroup$ Right. If you want to you can add a few cycles to make a flower :) $\endgroup$– PifagorFeb 3, 2014 at 23:58