📂Graph Theory

Walks, Trails, Paths, and Cycles in Graph Theory

Definition ¹

Let there be a given graph $G$.

1. A finite sequence of edges is called a walk and is denoted as follows: $$ v_{0} v_{1} , v_{1} v_{2} , \cdots , v_{m-1} v_{m} \\ v_{0} \rightarrow v_{1} \rightarrow v_{2} \rightarrow \cdots \rightarrow v_{m-1} \rightarrow v_{m} $$ Here, $v_{0}$ is called the initial vertex, $v_{m}$ is called the final vertex, and $m$ is called the length.
2. If all edges in a walk are different, it is called a trail.
3. If all vertices in a walk are different, it is called a path.
4. If the initial and final vertices of a walk are the same, it is called closed.
5. A closed path is called a cycle.

These concepts can be similarly defined for directed graphs as well, and can also be defined for infinite graphs as follows:

Let $G$ be an infinite graph. In the definitions below, walks can be replaced with trails, paths, cycles. 6. A (finite) walk is exactly the same as a walk in a conventional graph. 7. A one-way infinite walk is defined as follows: $$ v_{0} \to v_{1} \to v_{2} \to \cdots $$ 8. A two-way infinite walk is defined as follows: $$ \cdots \to v_{-2} \to v_{-1} \to v_{0} \to v_{1} \to v_{2} \to \cdots $$

Explanation

In the definition of a path, the initial and final vertices are exceptions. In other words, if $v_{0} = v_{m}$, it can be a path, hence a ‘closed path’ can exist. Meanwhile, in the definitions of a path and a trail, if all vertices are different, then all edges must also be different, so a path is also a trail.

A cycle is, simply put, a ’loop shape’ found in a graph, and it’s a concept widely used throughout graph theory. For example, the following figure shows that there are a total of three cycles in the graph:

Furthermore, the following theorem is known about cycles.

Theorem

If every vertex of a finite graph $G$ has a degree of $2$ or more, then $G$ contains a cycle.

Proof

Since $G$ would obviously contain a cycle if it has loops or multiple edges, we assume that $G$ is a simple graph.

Fix a random vertex $v_{0} \in V(G)$ and consider the following path: $$ v_{0} \to v_{1} \to v_{2} \to \cdots $$ As the degree of every vertex is $2$ or more, according to the assumption, it’s guaranteed that we can continue to select any vertex adjacent to the previous vertex $v_{i}$, excluding $v_{i-1}$. However, since $G$ is a finite graph, we will inevitably select a vertex $v_{k}$ that is already part of the path. Thus, the path $v_{k} \to \cdots \to v_{k}$, whose initial and final vertices are $v_{k}$, is confirmed to exist as a cycle in $G$.

■