Exercise 961Combinatorics › Graph theoryL1Added 3 Nov 2026

Hamiltonian cycles (example)

#Hamiltonian#cycle#NP-hard

Statement

Give an example of a graph with a Hamiltonian cycle but no Eulerian circuit.

Hint

A triangle with a pendant edge at each vertex.

Show solutionHide solution

Example. $G$ = cycle $1$ - $2$ - $3$ - $4$ - $5$ - $1$ plus pendant edges $1$ - $1'$ , $2$ - $2'$ , $3$ - $3'$ , $4$ - $4'$ , $5$ - $5'$ .

Hamiltonian. The cycle $1$ - $2$ - $3$ - $4$ - $5$ - $1$ visits all $10$ vertices.

Eulerian? No: the leaves $1',2',\ldots$ have degree $1$ (odd).

Conclusion. Hamiltonian cycle exists, Eulerian circuit does not.