Lesson 4

A walk in a graph is a sequence of edges such that each edge (except for the first one) starts with a node where the previous edge ended. The length of a walk is the number of edges in it. We say that a walk is closed if it starts and ends at the same node. A path is a walk where all edges are distinct. We say that a path is simple if all its nodes are distinct.

To give an example, consider the following graph where all edges are named for convenience.

It is sometimes convenient to specify a walk by its sequence of nodes (rather than edges). For example, \((P,Q,S)\) defines a walk \((e_{2}, e_{4})\) of length \(2\). In many cases, we will write \(P \to Q \to S\) instead of \((P,Q,S)\).

A cycle is a closed path (that is, its first node is the same as the last one). In particular, all edges of a cycle are distinct. A cycle is called simple if it contains no repeated nodes except for the first node and the last node.

In the graph above, \((e_{2},e_{3},e_{8},e_{4},e_{7},e_{6})\) is a cycle that starts and ends at the node \(Q\). It is not simple as it visits \(Q\) three times. However, \((e_{5},e_{4},e_{2},e_{3})\) is a simple cycle.

It is not difficult to see that if there is a path from a node \(u\) to a different node \(v\), then there is also a simple path. This is best illustrated with a toy example. For the graph above, a path \[U \to P \to Q \to S \to R \to Q \to T\] is not simple as it goes through the node \(Q\) twice. However, one can just cut everything between the two visits to \(Q\) to get a simple path: \[U \to P \to Q \to T\ .\]