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?
[Math] Connected graph – 5 vertices eulerian not hamiltonian
graph theoryhamiltonian-path
graph theoryhamiltonian-path
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?
Best Answer
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.