CMSC 27100 — Lecture 18

Walks, paths, cycles

A natural impulse when presented with a bunch of circles joined by lines is to see if we can get from one circle to another by following the lines. More formally, when we do this, what we're doing is checking if an object is connected to another object. It's not surprising to learn that this is a fundamental property of graphs that we'd like to work with.

A walk of length $k$ is a sequence of $k+1$ vertices $v_0, v_1, \cdots, v_k$ such that $v_{i-1}$ and $v_i$ are adjacent for $1 \leq i \leq k$—in other words, $(v_{i-1},v_i) \in E$. This walk has length $k$ because we traverse $k$ edges. A path is a walk without repeated vertices. A cycle of length $k$ is a path with the allowance/condition that $v_0 = v_k$ and no repeated edges.

Consider the following graphs.

In the first, the walk $a_0 a_1 a_4 a_2 a_1 a_3$ is highlighted in red. In the second, the path $b_0 b_4 b_2 b_3 b_1$ is highlighted in orange. In the third, the cycle $c_0 c_4 c_2 c_1 c_0$ is highlighted in yellow.

Note that the above definitions are not universal and you should be very careful when consulting other materials—in particular, the textbook uses "path" to mean walk and "simple path" to mean path.

Before we proceed, here is a simple theorem about walks and paths and how the fastest way between point $a$ and $b$ is a straight line.

Let $G$ be a graph and $u,v \in V$ be vertices. If there is a walk from $u$ to $v$, then there is a path from $u$ to $v$.

Consider the walk $u = v_0 v_1 \cdots v_k = v$ from $u$ to $v$ of minimum length $k+1$. Suppose that a vertex is repeated. In other words, there exist, $i, j$ with $i \lt j$ such that $v_i = v_j$. Then we can create a shorter walk $$u = v_0 v_1 \cdots v_{i-1} v_i v_{j+1} v_{j+2} \cdots v_k = v,$$ since $(v_i,v_{j+1}) = (v_j,v_{j+1})$. Then this contradicts the minimality of the length of our original walk. So there are no repeated vertices in our walk and therefore, it is a path by definition.

Another sort of 'common sense' theorem says that if we have two distinct paths, meaning they're not the same path, then we have a cycle in our graph. Be careful: distinct doesn't mean disjoint. In other words, the two paths can share some edges, but will contain different edges at some point.

Let $G = (V,E)$ be a graph and let $u,v \in V$. If there are two distinct paths between $u$ and $v$, then $G$ contains a cycle.

Consider two paths $P_1$ and $P_2$ between vertices $u$ and $v$. We can write $P_1 = a_0 a_1 \cdots a_m$ and $P_2 = b_0 b_1 \cdots b_n$, where $a_0 = b_0 = u$ and $a_m = b_n = v$, with $m$ not necessarily equal to $n$. Since the two paths are distinct, there is an edge that is in $P_1$ that is not in $P_2$. Let $(a_i,a_{i+1})$ be this edge.

Consider the graph $G - (a_i,a_{i+1})$—that is, the graph $G$ without the edge $(a_i, a_{i+1})$. Now, consider the walk $$a_i a_{i-1} \cdots a_0 = u = b_0 b_1 \cdots b_n = v = a_n a_{n-1} \cdots a_{i+1}.$$ This is a walk from $a_i$ to $a_{i+1}$ which does not use the edge $(a_i, a_{i+1})$. Therefore, there is a path between $a_i$ and $a_{i+1}$. Then the addition of the edge $(a_i,a_{i+1})$ creates a path from $a_i$ back to itself—a cycle. Therefore, $G$ contains a cycle.

Connectedness

What does it mean if there's a walk between two vertices? Practically speaking, it means that we can reach one from the other. This idea leads to the following definition.

A graph $G$ is connected if there is a walk between every pair of vertices.

The graphs that we've seen so far have mostly been connected. However, we're not guaranteed to work with connected graphs, especially in real-world applications. In fact, we may want to test the connectedness of a graph. For that, we'll need to talk about the parts of a graph that are connected.

A connected component of a graph $G = (V,E)$ is a connected subgraph $G'$ of $G$ that is not a proper subgraph of another connected subgraph of $G$.

Consider the following graph.

This graph has two connected components, the subgraphs induced by $a_0,\dots, a_5$ and $a_6,\dots,a_9$. No other can be considered a connected component since they would either be not connected or a proper subgraph of one of the two connected components we identified.