# Eulerian Circuits and Hamiltonian Cycles

Is there a fundamental relationship between circuits and cycles in an arbitrary graph? Are they mutually independent objects?

Thanks

-

A cycle with two chords has a Hamiltonian cycle but no Eulerian circuit.

A lemniscate ($\infty$, two cycles pasted at a vertex) has an Eulerian circuit but no Hamiltonian cycle.

A cycle has both a Hamiltonian cycle and an Eulerian circuit.

A star with at least 3 edges has neither a Hamiltonian cycle nor an Eulerian circuit.

Wikipedia describes the graphs which have Eulerian circuits; Hamiltonian cycles are much more complicated, and in particular it is very probable that there's no simple characterization of graphs that have them (unless P=NP).

-
By "path" do you mean "path graph"? –  user02138 Nov 24 '10 at 3:59
If so, how does a path graph have an Eulerian circuit? –  user02138 Nov 24 '10 at 4:01
Oh, I meant an Eulerian tour. Let me find another example. –  Yuval Filmus Nov 24 '10 at 4:07
Much better! –  user02138 Nov 24 '10 at 4:10
Just to clarify, by "cycle" Yuval means "cycle graph". –  user02138 Nov 24 '10 at 4:13