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 was just brushing up on my discrete mathematics specifically graph theory and read the following definition of a walk in a graph

"A walk in a graph is an alternating sequence of vertices and edges from a start vertex to an end vertex where start and the end vertices are not necessarily distinct"

and after this I read up the definition of a path in a graph which says

"A path in a graph is a walk in the graph with no repeated vertices"

the point of confusion is that the definition for a path doesn't mention anything about the repetition of edges in a path, although the idea of repetition of edge in a path sounds absurd to me because that eventually means that I am taking the same road that I traversed previously and hence repeating the same destinations which are the vertices respectively. I am curious to know if there is any such case of a path where there is a repetitive edge but no repeated vertex.

One more thing I would like to know is can there exists an ordering of edges in a graph such that the path from one vertex to another is infinite in short can there be an infinite path in a finite graph?

share|improve this question

1 Answer 1

up vote 2 down vote accepted

The terminology varies a bit from textbook to textbook, so it's always a good idea to check the conventions used by that particular author.

I assume that the definitions you work with are the ones you state. Then there can not be a repeated edge in a path. If an edge occurs twice in the same path, then both of its endpoints would also occur twice among the visited vertices.

For the second question, a finite graph has a finite number of edges and a finite number of vertices, so as long as no repetition are allowed, a path would have to be finitely long.

share|improve this answer
    
The thing is a walk can have repeated vertices and edges but a path is a special type of walk where no vertex is repeated –  AnkitSablok Jun 10 '13 at 13:02

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.