0

My Research

I've looked at two questions which seemed similar on MSE. The first one was inadequate for me because most of the answers where just stating book definitions, which I already have. The second one has all the same problems as the first, and doesn't offer me any more clarity than my book.

My Troubles

At User Request, Here is the definition of a walk:

enter image description here

My book gives the following definitions of the specific types of walks known as paths, trails, cycles and circuits

enter image description here

These definitions give me some trouble. How can can a path possibly be closed, as that means we would have to use the starting vertex twice(more than once making it, by definition, not a path). I really need to get a handle on what they mean by vertices and edges being repeated, because it doesn't seem to mean what I think it means. For computing walk length, do I count all the edges, what about repeated edges, do those count as well? Can someone show me some examples of what would and would not be a path, what would and would not be a trail, and what would be a walk of length $x$ (you can use whichever number you like)

Community
  • 1
Dunka
  • 2,787
  • 12
  • 41
  • 69
  • Somewhere before this definition should be a definition for a "walk." It looks like there's an issue with whether or not the vertex $x$, which is the starting vertex of the walk, is or isn't included in the vertex list. – Alex R. Mar 17 '15 at 19:43
  • @AlexR. I've uploaded the picture – Dunka Mar 17 '15 at 19:46
  • So for part (b), on the subject of a cycle, they meant that no vertex occurs twice, except for $x=y$. Then it looks like everything is consistent. – Alex R. Mar 17 '15 at 19:49
  • Thanks. Do you know what they mean precisely by repeated? Is it if a vertex has more than two edges connected to it? – Dunka Mar 17 '15 at 20:00
  • "Repeated" for the definition of a walk? They are referring to edges. So you can definitely visit vertices multiple times if they have more than one edge coming out of them. Think of "visiting no vertex twice" as a stronger condition than "visiting no edge twice." The former implies the latter but not the other way around. – Alex R. Mar 17 '15 at 20:02
  • I was wondering in context of a trail or path – Dunka Mar 17 '15 at 20:05
  • Sorry I'm confused. In the definition of trail, they plainly state no edge is repeated. Whereas for a path, no vertex is repeated. They implicitly define a closed path as a path with no repeated vertex except for $x=y$ for start/end vertices. – Alex R. Mar 17 '15 at 20:14

0 Answers0