0
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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?"). $\endgroup$ – hardmath Jul 2 '17 at 23:21
  • $\begingroup$ 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? $\endgroup$ – Michelle Jul 2 '17 at 23:31
  • $\begingroup$ 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". $\endgroup$ – hardmath Jul 2 '17 at 23:38
  • $\begingroup$ 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! $\endgroup$ – Michelle Jul 2 '17 at 23:41
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I think in our class we define single vertices as each having a tour that starts and ends at themselves, so I guess with that definition each vertex would have its own tour? But yes I understand what you are saying! $\endgroup$ – Michelle Jul 2 '17 at 23:36
  • $\begingroup$ In general, each connected component should have its own tour, but there is no way to get from one connected component to another one. $\endgroup$ – G Tony Jacobs Jul 2 '17 at 23:37
  • $\begingroup$ Ok this is what I just wanted to confirm, that by my definition of a tour every graph would have at least one. thanks! $\endgroup$ – Michelle Jul 2 '17 at 23:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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