12.2: Walks and Connectedness

Graphs can be connected or disconnected. Intuitively, this corresponds to the network being connected or disconnected – is it possible to travel from any node to any other node? When a graph (or network) is disconnected, it has broken down into some number of separate connected components - the pieces that still are connected.

Since this is mathematics, we require more formal definitions, to ensure that the meanings are not open to misunderstanding. Before we can define connectedness, we need the concept of a walk in a graph.

Definition: Walk

A walk in a graph \(G\) is a sequence of vertices \((u_1, u_2, . . . , u_n)\) such that for every \(1 ≤ i ≤ n − 1\), we have \(u_i ∼ u_{i+1}\). (That is, consecutive vertices in the walk must be adjacent.)

A \(u − v\) walk in \(G\) is a walk with \(u_1 = u\) and \(u_n = v\). (That is, a walk that begins at \(u\) and ends at \(v\).)

Now we can define what it means for a graph to be connected.

Definition: Word

The graph \(G\) with vertex set \(V\) is connected if for every \(u\), \(v ∈ V\), there is a \(u − v\) walk.

The connected component of \(G\) that contains the vertex \(u\), is

\[\{v ∈ V | \text{ there is a } u − v \text{ walk.}\}\]

This definition of connected component seems to depend significantly on the choice of the vertex \(u\). In fact, though, being in the same connected component of \(G\) is an equivalence relation on the vertices of \(G\), so the connected components of \(G\) are a property of \(G\) itself, rather than depending on particular choices of vertices. We won’t go through a formal proof that being in the same connected component is an equivalence relation (we leave this as an exercise below), but we will go through the proof of a proposition that is closely related.

Proposition \(\PageIndex{1}\)

Let \(G\) be a graph, and let \(u\), \(v\), \(w ∈ V (G)\). Suppose that \(v\) and \(w\) are in the connected component of \(G\) that contains the vertex \(u\). Then \(w\) is in the connected component of \(G\) that contains the vertex \(v\).

Proof

Since \(v\) and \(w\) are in the connected component of \(G\) that contains the vertex \(u\), by definition there is a \(u − v\) walk, and a \(u − w\) walk. Let \((u = u_1, u_2, . . . , u_k = w)\) be a \(u − w\) walk, and let \((u = v_1, v_2, . . . , v_m = v)\) be a \(u − v\) walk.

We need to show that \(w\) is in the connected component of \(G\) that contains the vertex \(v\); by definition, this is equivalent to showing that there is a \(v − w\) walk. Consider the sequence of vertices:

\[(v = v_m, v_{m−1}, . . . , v_1 = u = u_1, u_2, . . . , u_k = w).\]

Since \((u = v_1, v_2, . . . , v_m = v)\) is a \(u − v\) walk, consecutive vertices are adjacent, so consecutive vertices in the first part of the given sequence (from \(v_m\) through \(v_1 = u\)) are adjacent. Similarly, since \((u = u_1, u_2, . . . , u_k = w)\) is a \(u − w\) walk, consecutive vertices are adjacent, so consecutive vertices in the last part of the given sequence (from \(u = u_1\) through \(u_k\)) are adjacent. Therefore, the given sequence is in fact a \(v − w\) walk, as desired.

When discussing walks, it is convenient to have standard terminology for describing the length of the walk.

Definition: Length of a Walk

The length of a walk is one less than the number of vertices in the walk. Thus, if we think of a walk as a sequence of edges (formed by consecutive pairs of vertices from the walk), the length of the walk is the number of edges in the walk.

Unfortunately, there is some disagreement amongst mathematicians as to whether the length of a walk should be used to mean the number of vertices in the walk, or the number of edges in the walk. We will use the latter convention throughout this course because it is consistent with the definition of the length of a cycle (which will be introduced in the next section). You should be aware, though, that you might find the other convention used in other sources.

Sometimes it is obvious that a graph is disconnected from the way it has been drawn, but sometimes it is less obvious. In the following example, you might not immediately notice whether or not the graph is connected.

Example \(\PageIndex{1}\)

Consider the following graph.

Find \(a\) walk of length \(4\) from \(a\) to \(f\). Find the connected component that contains \(a\). Is the graph connected?

Solution

A walk from of length \(4\) from \(a\) to \(f\) is \((a, c, a, c, f)\). (Notice that the vertices and edges used in a walk need not be distinct.) Remember that the length of this walk is the number of edges used, which is one less than the number of vertices in the sequence!

The connected component that contains \(a\) is \(\{a, c, e, f\}\). There are walks from \(a\) to each of these vertices, but there are no edges between any of these vertices and any of the vertices \(\{b, d, g, h\}\).

Since there is no walk from \(a\) to \(b\) (for example), the graph is not connected.

Exercise \(\PageIndex{1}\)

1) Prove that being in the same connected component of \(G\) is an equivalence relation on the vertices of any graph \(G\).

2) Is the following graph connected? Find the connected component that contains \(a\). Find a walk of length \(5\) from \(a\) to \(f\).

3) Is the following graph connected? Find the connected component that contains \(a\). Find a walk of length \(3\) from \(a\) to \(d\).

4) Use Euler’s Handshaking Lemma to prove (by contradiction) that if \(G\) is a connected graph with \(n\) vertices and \(n − 1\) edges, and \(n ≥ 2\), then \(G\) has at least \(2\) vertices of valency \(1\).

[Hint: What does \(G\) being connected imply about \(d(v)\) for any vertex \(v\) of \(G\)?]

5) Fix \(n ≥ 1\). Prove by induction on \(m\) that for any \(m ≥ 0\), a graph with \(n\) vertices and \(m\) edges has at least \(n − m\) connected components.