Connected graph - 5 vertices eulerian not hamiltonian

22.7k Views Asked by At

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?

2

There are 2 best solutions below

2
On BEST ANSWER

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

0
On

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.