Can a walk be equivalently viewed as a graph? https://en.wikipedia.org/wiki/Path_(graph_theory)#Walk,_trail,_path says


*

*A walk is a finite or infinite sequence of edges which joins a sequence of vertices. Let G = (V, E, ϕ) be a graph. A finite walk is a
sequence of edges (e1, e2, …, en − 1) for which there is a sequence of
vertices (v1, v2, …, vn) such that ϕ(ei) = {vi, vi + 1} for i = 1, 2,
…, n − 1. (v1, v2, …, vn) is the vertex sequence of the walk. This
walk is closed if v1 = vn, and open else. An infinite walk is a
sequence of edges of the same type described here, but with no first
or last vertex, and a semi-infinite walk (or ray) has a first vertex
but no last vertex.


*A trail is a walk in which all edges are distinct.


*A path is a trail in which all vertices (and therefore also all edges) are distinct.

Is it correct that

*

*A walk is by definition a sequence of edges, so a walk is not a graph?


*A path, which is defined as a special walk, is not a graph by definition? A lot of graph theory books say that a path is a graph. Are these two different meanings of a path equivalent?


*Can a walk be equivalently viewed as a graph? ("equivalently" means without loss of information. Since a walk may repeat an edge, while a graph's edge set doesn't contain an edge more than once, I doubt a walk can be equivalently viewed as a graph)


*Can a trail be equivalently viewed as a graph? (I guess so, because a trail is defined to not have repeated edges, which makes it equivalent to a graph)
Thanks.
 A: The two notions of a path are as follows:

*

*A "path graph": a graph isomorphic to one with $n$ vertices $v_1, v_2, \dots, v_n$ and $n-1$ edges $v_1 v_2, v_2 v_3, \dots, v_{n-1} v_n$. Commonly denoted $P_n$.

*A path inside a graph $G$. Sometimes this is defined as a type of walk, as you did; less commonly, this is defined as a subgraph of $G$ isomorphic to $P_n$ (for some $n$).


The most careful way to define a walk is a sequence of vertices and edges: $v_0, e_1, v_1, e_2, v_2, \dots, e_n, v_n$, where each edge $e_i$ joins $v_{i-1}$ to $v_i$. But of course just the sequence of edges is enough to infer the vertices. In a simple graph, the sequence of vertices is also enough to infer the edges, so we could use either definition.
For any walk in a graph $G$, we could instead consider the subgraph of $G$ consisting of all the edges included in the walk. But we always lose some information by doing this.

*

*In the case of a walk, as you've noticed, we lose the most information. An edge could be part of the walk multiple times, and the subgraph idea forgets all about that.

*Even for a trail, we forget some information by passing to the subgraph. Suppose we have a complete graph on vertices $1,2,3,4,5$. The closed trail that goes $1 \to 2 \to 3 \to 1 \to 4 \to 5 \to 1$ is different in many ways from the trail that goes $5 \to 4 \to 1 \to 2 \to 3 \to 1 \to 5$, but they have the same edge set. Or, take any Eulerian graph: there could be many different Eulerian trails, but they would all give the same subgraph, which is the whole graph.

*We lose almost no information for a path, but we still lose one thing: orientation. We might want to distinguish the paths $1 \to 2 \to 3 \to 4 \to 5$ and $5 \to 4 \to 3 \to 2 \to 1$, but they definitely give the same subgraph.

Sometimes, though, we want to lose the information, and consider the subgraph instead of the sequence. This is especially common for cycles: closed walks in which no vertex is repeated except for the first and the last vertex being the same. If we take an $n$-vertex cycle, there are $2n$ closed walks total with that set of edges: we can start at any of $n$ vertices, and go in either of $2$ directions. But we don't really think of those as different cycles.
