Walks, Trails, Paths, Extremal¶
Up until now, what we've seen of graphs didn't have much difference from common mathematical structures like lists and sets. However, with the definitions in this section, we can prove theorems that would appear very complex without the use of graphs.
Walk¶
A sequence like \(v_1e_1v_2e_2...v_{k-1}e_{k-1}v_k\) is called a walk if and only if the v's are vertices and the e's are edges, and each edge is placed between its corresponding two vertices. If we consider a graph as a city where its roads are the edges of the graph, the movement of a creature in this city is a walk.
If the starting and ending vertices of a walk are the same (the creature has returned to its starting point), this walk is called a closed walk.
In the graph above, \(a1b4d6d\), \(b1a1b2a1b3c\), and \(a1b4d5c3b4d4b2a\) are examples of walks. The last walk is a closed walk. The length of a walk is defined as the number of its edges. The walks above have lengths 3, 5, and 7, respectively. If the graph were simple, stating the sequence of vertices would be sufficient, and there would be no need to name the edges and specify them within the walk.
Trail¶
A trail is a walk that does not have repeated edges. A trail whose start and end vertices are the same is called a closed trail, similar to the previous section.
In the graph above, \(a1b4d6d\) and \(a1b4d5c3b2a\) are examples of trails. The last trail is a closed trail.
Path and Cycle¶
A path is a walk that does not have repeated vertices. It is clear that every path is also a trail. By definition, a path whose start and end vertices are the same does not exist (with the exception of single-vertex paths or paths of length zero). However, if in a walk, only the start and end vertices are the same, that walk is called a cycle. Single-vertex walks (zero-edge or zero-length) are not considered cycles. If a graph is simple, it does not have cycles of length one or two.
In the graph above, \(a1b3c5d\) is a path, and \(a1b2a\), \(d6d\), and \(b3c5d4b\) are cycles of this graph.
Some Examples¶
Although the definitions above are simple, they will greatly assist us in proving graph theorems. Below, we will see a few examples together.
If there is a walk between two vertices, there is a path between them¶
A walk between two vertices u and v refers to a walk whose starting vertex is u and ending vertex is v. To prove the statement, it is sufficient to consider, among all walks between these two vertices, the walk that has the fewest edges. This walk is a path because if it had a repeated vertex, meaning the walk was of the form
then a walk with fewer edges would exist (the walk below)
which contradicts our assumption.
If the degree of all vertices is at least 2, there is a cycle in the graph¶
Cycle-free graphs have interesting properties that we will extensively explore in Chapter 2. But for now, we content ourselves with this theorem: in a cycle-free graph, there must be a vertex with a degree less than 2.
To prove this, we consider the longest path (i.e., a path with the maximum possible number of edges). Note that if we considered the longest walk in our argument, our argument would not be valid and might lead to incorrect results, because the longest walk might not exist. However, since every path has at most n vertices and thus n-1 edges, we can consider the longest path existing in the graph.
The starting vertex of this path cannot have an edge to a vertex outside this path (e.g., the red vertex) because in that case, a longer path would exist. So all edges of this vertex are within this path. And since the degree of this vertex is at least 2, besides its adjacent vertex in the path, it must also have an edge to another vertex (the dashed edge), and this means a cycle exists.
The edges of any graph where all degrees are even can be partitioned into cycles¶
If the graph has no edges, the claim is proven. Otherwise, if we ignore vertices of degree zero, a cycle exists in the graph according to the proposition above. We consider that cycle as one set of the partition and remove it. The degrees of the vertices within the cycle are reduced by exactly two, and therefore the degrees of the resulting graph also remain even. We continue this process until the graph becomes empty of edges, and thus the desired partition is obtained.
Some Other Definitions¶
Length of a Walk: As mentioned, the number of edges in a walk is called its length. This definition extends to trails and paths as well. For example, as we read, \(P_n\) is a path graph. The length of this path is \(n-1\).
Distance Between Two Vertices: The length of the shortest path between two vertices is called the distance between them. If no path exists, the distance is defined as infinity.
Girth of a Graph: The length of the shortest cycle in a graph that has more than 2 vertices. If a graph has no cycles, its girth is defined as infinity.
Hamiltonian Path and Cycle: Refers to a path or cycle that includes all vertices of the graph.
This book is made by The Shaazzz contributors.
It is publicly available with cc-by-sa license.
Last updated at اکتبر 13, 2025.
Rendered by Sphinx (4.3.2) and Minoo theme (Beta 0.9.7).
