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?
Best Answer
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.