I understand the conditions necessary for a graph to have Eulerian and Hamiltonian paths.
I could find examples for graphs that are Eulerian but not Hamiltonian.
Can someone give me graphs that are non-Eulerian but are Hamiltonian?
[Math] Graphs that are non-Eulerian but are Hamiltonian
eulerian-pathgraph theoryhamiltonian-path
Related Solutions
- No, because line graph $L(K_4)$ of graph $K_4$ is connected and $4$-regular, therefore is Eulerian, but $K_4$ is not Eulerian.
- No, because $C_5$ is Hamiltonian, but $L(C_5) \cong C_5$ is not Hamilton-connected.
- Yes. Hamiltonian cycle of graph $H$ obviously is a dominating circuit in $H$, independently of whether $H$ is a line graph of some graph or not.
It is not the case that every Eulerian graph is also Hamiltonian. It is required that a Hamiltonian cycle visits each vertex of the graph exactly once and that an Eulerian circuit traverses each edge exactly once without regard to how many times a given vertex is visited. Take as an example the following graph:
It's easy to find an Eulerian circuit, but there is no Hamiltonian cycle because the center vertex is the only way one can get from the left triangle to the right.
Best Answer
Make a cycle on $4$ or more vertices. Then join two unjoined vertices with an edge. Then join two different unjoined vertices with an edge.