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.

I'm reading Combinatorics and Graph Theory, 2nd Ed., and am beginning to think the terms used in the book might be outdated. Check out the following passage:

If the vertices in a walk are distinct, then the walk is called a path. If the edges in a walk are distinct, then the walk is called a trail. In this way, every path is a trail, but not every trail is a path. Got it?

On the other hand, Wikipedia's glossary of graph theory terms defines trails and paths in the following manner:

A trail is a walk in which all the edges are distinct. A closed trail has been called a tour or circuit, but these are not universal, and the latter is often reserved for a regular subgraph of degree two.

Traditionally, a path referred to what is now usually known as an open walk. Nowadays, when stated without any qualification, a path is usually understood to be simple, meaning that no vertices (and thus no edges) are repeated.

Am I to understand that Combinatorics and Graph Theory, 2nd Ed. is using a now outdated definition of path, referring to what is now referred to as an open walk? What are the canonical definitions for the terms "walk", "path", and "trail"?

share|improve this question
2  
You seem to have misunderstood something: the definitions in the book are the same as those given as current by Wikipedia. –  Brian M. Scott Oct 7 '13 at 2:37
    
You may be right. Specifically, I only just realized that paths have distinct vertices, whereas trails have distinct edges. –  modocache Oct 7 '13 at 2:42
    
Indeed you are right, I misread the text. If you post your comment as an answer I'd gladly accept it. –  modocache Oct 7 '13 at 2:45
    
Done — and perhaps a little more clearly. –  Brian M. Scott Oct 7 '13 at 2:47
add comment

3 Answers

up vote 4 down vote accepted

You seem to have misunderstood something, probably the definitions in the book: they’re actually the same as the definitions that Wikipedia describes as the current ones.

share|improve this answer
add comment

Today I also faced the same problem for reading these very first concepts. My understanding is as follows.

Path: A path is a simple graph whose vertices can be ordered so that two vertices are adjoint iff they are constitutive in the list.

Walk: it is a list of vertices and edges $v_0, e_1, v_1, \dots, e_k, v_k$ for $1\le i \le k$, $e_i$ has an endpoints $v_{i-1}, v_i$.

Trial: It is an walk with no repeated edge.

share|improve this answer
add comment

A walk of length k is a non-empty alternating sequence of vertices and edges in G.

A walk is a trail if any edge is traversed at most once.

A trail is a path if any vertex is visited at most once except possibly the initial and terminal vertices when they are the same.

share|improve this answer
add comment

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.