Connected Graphs and Walks

Look at the diagram above. Starting at $A$, list every vertex you could reach by moving along edges. Is $E$ among them? Could any amount of cleverness get you there?

A graph is connected when it is in one piece, so that some route along edges joins every pair of vertices. A walk is such a route written down: an alternating sequence of vertices and edges, with each edge joining the vertices either side of it.

A graph is connected if, starting from any vertex, you can reach any other by moving along edges. It is in one piece.

A graph that is not connected splits into components. Each component is itself connected, and no edge joins one component to another. The graph in the diagram has two components: $\{A, B, C, D\}$ and $\{E, F\}$.

To test connectedness, pick any vertex and explore. Mark it, mark everything reachable from it in one step, then everything reachable from those, and continue until nothing new appears. If every vertex has been marked, the graph is connected. If not, the marked vertices form one component and the argument repeats on what is left.

Starting vertex does not matter. If the graph is connected, exploring from any vertex reaches everything, so any choice settles the question.

Connectedness is a precondition for most of what follows, and questions state it for that reason rather than as decoration.

Euler's formula gives $2$ only for connected graphs; a graph in $k$ pieces gives $k + 1$, as Lesson 5 showed.

An Eulerian trail, coming in Lesson 8, uses every edge of the graph. If the graph has two components, no single journey can reach the edges of both, so the question is settled before it is asked.

A disconnected graph is not a broken graph. It is a perfectly good object that certain results simply do not apply to, and noticing which is part of using them correctly.

In applications the check is often the whole question. "Can every suburb reach the hospital?" is a connectedness question about the bus network, and the answer is yes exactly when the relevant vertices lie in one component.

A walk is a route through the network, written as an alternating sequence of vertices and edges. Each edge in the sequence must join the vertex before it to the vertex after it.

In practice only the vertices are written, since the edges are then implied:

$A \to B \to C \to B \to D$

That is a legitimate walk provided the edges $AB$, $BC$, $CB$ and $BD$ all exist. Note that it visits $B$ twice and uses the edge between $B$ and $C$ twice, once in each direction.

A walk has no restrictions at all beyond following existing edges. Repeats of every kind are allowed, and the next lesson is entirely about what happens when they are forbidden.

Where a graph has multiple edges between the same pair of vertices, the vertex list becomes ambiguous and the edges must be named as well, since it matters which of the two was used.

The length of a walk is the number of edges it uses, counting a repeated edge each time it is used.

The walk $A \to B \to C \to B \to D$ lists five vertices and has length $4$. In general the length is one less than the number of vertices written, because each step from one vertex to the next uses one edge.

A walk is closed if it finishes where it started, and open otherwise. The walk $A \to B \to C \to A$ is closed; $A \to B \to C$ is open.

A single vertex on its own counts as a closed walk of length $0$, which sounds like a technicality and matters when a definition has to cover every case without exception.

Open and closed is the second of the two questions that the next lesson uses to classify journeys, the first being which repeats are allowed.

Given a graph and a sequence of vertices, deciding whether it is a walk is mechanical: take the vertices in consecutive pairs and check each pair is joined by an edge.

For the graph with edges $PQ$, $QR$, $RS$, $SP$, the sequence $P \to Q \to R \to S$ is a walk, since $PQ$, $QR$ and $RS$ all exist.

The sequence $P \to R \to S$ is not, because there is no edge $PR$. The two vertices are both in the graph and are connected by a longer route, but a walk must list every vertex it passes through, and this sequence skips $Q$ or $S$.

This is the commonest error: writing the destinations rather than the route. A walk records every step, not the interesting stops.

Five items on connectedness and walks. For each proposed walk, check consecutive pairs against the edge list.

1. 1 A graph has edges $AB$, $BC$, $DE$. Is it connected?

   Show answer
   Explore from $A$: you reach $B$ and $C$ but never $D$ or $E$.No; two components

2. 2 How many components does a graph with edges $PQ$, $QR$, $ST$, $UV$ have?

   Show answer
   $\{P, Q, R\}$, $\{S, T\}$ and $\{U, V\}$.$3$

3. 3 A walk lists $7$ vertices. What is its length?

   Show answer
   Each step between consecutive vertices uses one edge.$6$

4. 4 In a graph with edges $AB$, $BC$, $CD$, is $A \to B \to A \to B \to C$ a walk?

   Show answer
   Every consecutive pair must be an edge; repeats are allowed.Yes, of length $4$

5. 5 In a graph with edges $AB$, $BC$, $CD$, is $A \to C$ a walk?

   Show answer
   Check whether $AC$ is an edge.No