Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

Thanks

share|improve this question

3 Answers 3

up vote 3 down vote accepted

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).

share|improve this answer
    
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

Even for planar 3-connected graphs, which are the vertex-edge graphs that arise from convex 3-dimensional polyhedra, one can have all four possibilities: non-HC and non-Eulerian graphs, non-HC and Eulerian graphs; HC and Non-Eulerian graphs; HC and and Euler graphs, where HC means has a Hamiltonian circuit, and Eulerian means has an Eulerian circuit. (It is well known that a connected graph has an Eulerian circuit if and only if it is even-valent.)

However, for planar and 3-connected graphs it is of considerable interest to look at operations on the graphs that preserve the property of having an HC or Eulerian circuit or special kinds of Eulerian circuits. For example if G is plane, 3-connected and has an HC when does the dual of G have an HC? When does the medial graph for G have an HC, etc.? A famous problem which remains open is known as Barnette's conjecture: Does every 3-valent, bipartite, plane, 3-connected graph have an HC? It is also unkown if all the planar 3-connected 3-valent graphs with exactly 12 pentagons and some number of hexagonal faces have HC's. (There graphs are known as the fullerenes.)

share|improve this answer

By definition a path graph cannot have an Eulerian circuit or a Hamiltonian cycle. A loop graph (consisting of one edge and one vertex) has both an Eulerian circuit and a Hamiltonian cycle. As above, there are examples where a graph might have one but not the other. The answer to your question is that there is no fundamental relationship between the two.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.