# Does every graph have a tour?

Does every graph have a tour?

Not every graph has a cycle, but can it be said that every graph, even disconnected, has a tour since there are really no restrictions on repeating edges or vertices so you can just backtrack to get back to the original vertex?

In my class a tour is a walk that starts and ends at the same vertex, and a walk is a sequence of consecutive edges which may have repeated vertices.

• Definitions are your friends. Perhaps your definition of "a tour" has no restrictions on repeating edges or vertices, but if it is to have any value as a definition, it probably does have some restrictions. State your definition of "tour" so that Readers are better able to answer your Question ("does every graph have a tour?"). – hardmath Jul 2 '17 at 23:21
• in my class a tour is a walk that starts and ends at the same vertex, and a walk is a sequence of consecutive edges which may have repeated vertices. I am assuming a walk can also have repeated edges because Eulerian tours are a subset of tours and those are defined as tours using each edge exactly once? – Michelle Jul 2 '17 at 23:31
• So the "null" tour that goes nowhere (starts and ends at the same vertex) would satisfy the definition? Other authors use definitions that differ significantly from yours, particularly in requiring no repeated edges and (in other contexts) a requirement on the vertices to be "visited". – hardmath Jul 2 '17 at 23:38
• yes, the notes were not clear on whether a walk can have repeated edges so I think I will go clarify.. I'm seeing now how my question is more just subject to definitions, but thanks for responding! – Michelle Jul 2 '17 at 23:41

Any connected graph has a tour, but how could a disconnected graph have one? Consider the graph consisting of $2$ vertices and no edges. There is no tour possible there.