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 it contains $k$ edges. A path is a walk without repeated vertices—that is, if $i \neq j$, then $v_i \neq v_j$.
We say a closed walk is a walk that begins and ends at the same vertex. A cycle is a closed walk of length at least 3 with distinct vertices except for the beginning and end vertices.
Some notes on edge cases.
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.
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.
One question we can ask is what counts as a distinct cycle. For instance, in our example above, $c_0 c_1 c_2 c_4 c_0$ is a cycle and $c_0 c_2 c_3 c_4$ is a different cycle, but is $c_1 c_2 c_4 c_0 c_1$ a different cycle from the first one we described? Though our description is not the same, intuitively, it seems like we've described the same cycle.
To try to capture this notion, we'll give an alternative definition for cycles via the notion of subgraphs.
A graph $G' = (V',E')$ is a subgraph of a graph $G = (V,E)$ if $V' \subseteq V$ and $E' \subseteq E$.
Consider the following graphs from an earlier example:
We had said earlier that the graph on the left is 2-colourable while the one on the right is not. The explanation for this was that the one on the right has a triangle. Now, using the language of subgraphs and isomorphism, we can say this more formally: the graph contains a subgraph ismorphic to $K_3$.
The subgraph isomorphism problem asks whether given graphs $G$ and $H$ whether there is a subgraph of $G$ that is isomorphic to $H$. This problem is known to be hard to solve: it's NP-complete, which means that if we have a solution for the problem, we can check it efficiently, but we have no efficient algorithms for solving it. It's not hard to see that graph isomorphism is a special case of subgraph isomorphism.
So an alternative definition for a cycle in a graph is the following:
A cycle of a graph $G$ is a subgraph of $G$ that is isomorphic to the cycle graph $C_n$ for some $n \geq 3$.
In our example above, it's clear that the cycles $c_0 c_1 c_2 c_4 c_0$ and $c_1 c_2 c_4 c_0 c_1$ form the same subgraph. However, the cycle $c_0 c_2 c_1 c_4 c_0$, while defined on the same vertex, forms a different subgraph because we take different edges, so this would be considered a different cycle.
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$.
Here, we use "proper" in the same way as "proper subset"—since a graph can be a subgraph of itself, a proper subgraph is a subgraph that is not the graph itself.
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.
Another question related to connectivity that we can ask is how fragile the graph is. For instance, if we imagine some sort of network (computer, transportation, social, etc.), this is the same as asking where the points of failure are in our network. Which edges do we need to take out to disconnect our graph?
Let $G = (V,E)$ be a graph and consider an edge $e \in E$. If removing $e$ increases the number of connected components, then $e$ is a cut edge or bridge.
Consider the following graph $G$. There are two obvious bridges here: $(a_3,c_2)$ and $(b_2,c1)$.
We would like to be able to identify which edges are bridges and their properties. Some observation leads us to the following theorem which we'll prove next class.
Let $G$ be a graph. An edge $e$ of $G$ is a bridge if and only if it is not contained in any cycle of $G$.