The Central Idea
A graph tells us which vertices are adjacent. A route through the graph uses those adjacency relationships one after another.
The broadest route concept in this lesson is a walk. Additional restrictions produce trails and paths.
Under the conventions used here,
\[ \boxed{\text{path}\subseteq\text{trail}\subseteq\text{walk}}. \]Every path is a trail, and every trail is a walk, but the converses need not be true.
A Running Graph
Consider the undirected graph with
\[ V=\{a,b,c,d,e\} \]and
\[ E= \bigl\{ \{a,b\},\{a,c\},\{b,c\},\{b,d\},\{c,d\},\{d,e\} \bigr\}. \]We will use this graph to compare walks, trails, paths, and circuits.
The Running Graph as a Picture
What Is a Walk?
A walk is a sequence of vertices in which each consecutive pair is joined by an edge.
A walk can be written
\[ v_0,v_1,v_2,\ldots,v_k \]provided
\[ \{v_{i-1},v_i\}\in E \]for every \(i=1,\ldots,k\).
Walks May Repeat
A walk may repeat vertices, and it may also repeat edges.
For example,
\[ a,b,c,b,d \]is a walk in the running graph.
The vertex \(b\) appears twice, and the route remains valid because every consecutive pair is adjacent.
Example of a Repeated Edge
The sequence
\[ a,b,a,c \]is also a walk.
It uses the edge \(\{a,b\}\) from \(a\) to \(b\) and then uses the same undirected edge again from \(b\) back to \(a\).
Repeating an edge is permitted in a walk.
Length of a Walk
The length of a walk is the number of edges traversed.
The walk
\[ a,b,c,d,e \]uses four edges, so its length is
\[ \boxed{4}. \]A sequence with \(k+1\) listed vertices has length \(k\).
The Trivial Walk
A single vertex by itself is a walk of length \(0\).
For example,
\[ a \]is a valid trivial walk.
No edge is traversed.
What Is a Trail?
A trail is a walk that does not repeat any edge.
\[ \boxed{\text{trail}=\text{walk with no repeated edges}}. \]Vertices may repeat in a trail as long as no edge is used more than once.
Example of a Trail
In the running graph,
\[ a,b,c,a \]is a trail.
It uses
\[ \{a,b\},\qquad\{b,c\},\qquad\{c,a\}, \]and no edge repeats.
The starting vertex \(a\) appears again at the end, which is allowed.
A Walk That Is Not a Trail
The walk
\[ a,b,a,c \]is not a trail because the edge
\[ \{a,b\} \]is used twice.
What Is a Path?
In this text, a path is a walk in which no vertex is repeated.
\[ \boxed{\text{path}=\text{walk with no repeated vertices}}. \]Since repeating an edge would force repetition of its endpoints, every path is automatically a trail.
Example of a Path
The sequence
\[ a,b,d,e \]is a path.
Every consecutive pair is adjacent, and the vertices
\[ a,b,d,e \]are all distinct.
A Trail That Is Not a Path
The sequence
\[ a,b,c,a \]is a trail because no edge repeats.
It is not a path under our convention because the vertex \(a\) repeats.
Terminology Can Vary
Graph-theory terminology is not completely uniform across textbooks.
Some authors use path for what this lesson calls a walk and use simple path for a path with no repeated vertices.
Throughout Malone Math, this lesson uses:
- walk: repetitions allowed;
- trail: no repeated edges;
- path: no repeated vertices.
Open and Closed Walks
A walk is closed if it begins and ends at the same vertex.
A walk is open if its starting and ending vertices are different.
Thus,
\[ a,b,c,a \]is closed, while
\[ a,b,d,e \]is open.
What Is a Circuit?
A circuit is a closed trail.
\[ \boxed{\text{circuit}=\text{closed walk with no repeated edges}}. \]The starting vertex appears again at the end, but no edge is repeated.
Example of a Circuit
The sequence
\[ a,b,c,a \]is a circuit because it begins and ends at \(a\) and uses each of the edges
\[ \{a,b\},\qquad\{b,c\},\qquad\{c,a\} \]exactly once.
Closed Walk versus Circuit
Every circuit is a closed walk, but not every closed walk is a circuit.
For example,
\[ a,b,a \]is a closed walk in an undirected graph, but it repeats the edge \(\{a,b\}\), so it is not a trail and therefore not a circuit.
Cycles
A cycle is a closed route in which no vertex repeats except that the starting vertex is repeated at the end.
Thus,
\[ a,b,c,a \]is a cycle.
A cycle is a particularly simple kind of circuit.
Circuit versus Cycle
A circuit may revisit a vertex as long as no edge repeats.
A cycle is more restrictive: apart from the repeated start/end vertex, its vertices are distinct.
Therefore,
\[ \boxed{\text{cycle}\subseteq\text{circuit}}. \]Example: Circuit That Is Not a Cycle
Suppose a graph contains the edges needed for
\[ a,b,c,a,d,e,a. \]If no edge repeats, this route is a circuit.
But the vertex \(a\) occurs internally between the beginning and end, so the circuit is not a cycle.
Comparing the Route Types
| Route Type | May Repeat Vertices? | May Repeat Edges? | Must Be Closed? |
|---|---|---|---|
| Walk | Yes | Yes | No |
| Trail | Yes | No | No |
| Path | No | No | No |
| Circuit | Yes | No | Yes |
| Cycle | Only start/end | No | Yes |
Endpoints of a Path
The first and last vertices of a path are its endpoints.
For
\[ a,b,d,e, \]the endpoints are
\[ \boxed{a\text{ and }e}. \]The intermediate vertices are \(b\) and \(d\).
A Path between Two Vertices
If a path begins at \(u\) and ends at \(v\), we may call it a \(u\)-\(v\) path.
For example,
\[ a,b,d,e \]is an \(a\)-\(e\) path.
Reachability
A vertex \(v\) is reachable from a vertex \(u\) if there is a path from \(u\) to \(v\).
In an undirected graph, if \(v\) is reachable from \(u\), then \(u\) is reachable from \(v\) by traversing the same path in reverse.
Example: Reachability
In the running graph,
\[ a,b,d,e \]is a path from \(a\) to \(e\).
Therefore,
\[ \boxed{e\text{ is reachable from }a}. \]Connected Graphs
An undirected graph is connected if every pair of vertices can be joined by a path.
Equivalently, for every
\[ u,v\in V, \]there exists a \(u\)-\(v\) path.
The Running Graph Is Connected
In the running graph, every vertex can reach every other vertex.
For example, \(a\) can reach \(e\) through
\[ a,b,d,e. \]Since analogous paths exist between every pair of vertices, the graph is connected.
Disconnected Graphs
An undirected graph is disconnected if at least one pair of vertices has no path between them.
For example, suppose
\[ V=\{a,b,c,d\} \]and
\[ E=\bigl\{\{a,b\},\{c,d\}\bigr\}. \]There is no path from \(a\) to \(c\), so the graph is disconnected.
Connected Components
A connected component is a maximal connected part of a graph.
In
\[ E=\bigl\{\{a,b\},\{c,d\}\bigr\}, \]the vertex sets
\[ \{a,b\} \]and
\[ \{c,d\} \]form two connected components.
What “Maximal” Means Here
A component is not merely any connected collection of vertices.
It is maximal in the sense that no additional vertex from the graph can be added while keeping that subgraph connected.
Components divide an undirected graph into its separate connected regions.
Isolated Vertices as Components
An isolated vertex has degree \(0\).
It is still a connected component by itself.
If \(z\) is isolated, then
\[ \boxed{\{z\}} \]is a one-vertex component.
Counting Components
A connected graph has exactly one connected component.
A disconnected graph has two or more connected components.
Therefore,
\[ \boxed{\text{connected}\iff\text{exactly one component}}. \]Paths and Weighted Graphs
In a weighted graph, a path still has a length measured by its number of edges.
It may also have a total weight obtained from the edge weights.
For additive weights,
\[ w(P)=\sum_{e\in P}w(e). \]Path length and path weight remain different quantities.
Directed Walks
In a directed graph, a walk must follow the directions of the edges.
If the graph contains
\[ a\to b,\qquad b\to c, \]then
\[ a,b,c \]is a directed walk.
The reverse sequence is not valid unless the reverse directed edges also exist.
Directed Reachability
In a directed graph, \(v\) is reachable from \(u\) if there is a directed path from \(u\) to \(v\).
Directed reachability need not be symmetric.
It is possible that
\[ u\leadsto v \]while no directed path exists from \(v\) back to \(u\).
Strong Connectivity
A directed graph is strongly connected if every vertex can reach every other vertex by directed paths.
Thus, for every pair \(u,v\),
\[ u\leadsto v \]and
\[ v\leadsto u. \]Weak Connectivity
A directed graph is weakly connected if replacing its directed edges by undirected edges produces a connected undirected graph.
Weak connectivity ignores arrow direction when testing whether the graph is structurally in one piece.
Strong Connectivity Is More Demanding
Consider
\[ a\to b\to c. \]Ignoring direction gives the connected chain
\[ a-b-c. \]So the digraph is weakly connected.
But \(c\) cannot reach \(a\), so it is not strongly connected.
Why Paths Matter
Paths formalize the idea of getting from one vertex to another without revisiting vertices.
They support many later questions:
- Can one vertex reach another?
- What is the shortest route?
- Does a graph contain a cycle?
- Is the graph connected?
- Can all vertices be linked without redundancy?
- Can every edge or every vertex be visited under special restrictions?
Removing Repetition from a Walk
In an undirected graph, if a walk exists from \(u\) to \(v\), then a path also exists from \(u\) to \(v\).
Repeated portions can be removed until no repeated vertex remains.
This is why reachability may be defined using paths even though walks are more general.
Example: Simplifying a Walk
Suppose
\[ a,b,c,b,d,e \]is a walk.
The section
\[ b,c,b \]leaves \(b\) and returns to \(b\).
Removing that detour gives
\[ a,b,d,e, \]which is a path from \(a\) to \(e\).
Common Error: Calling Every Walk a Path
Under the convention used here, a path cannot repeat a vertex.
Therefore,
\[ a,b,c,b,d \]is a walk but not a path because \(b\) repeats.
Common Error: Confusing Trail and Path
A trail forbids repeated edges.
A path forbids repeated vertices.
The sequence
\[ a,b,c,a \]can be a trail while failing to be a path.
Common Error: Calling Every Closed Walk a Circuit
A circuit must be a closed trail.
If a closed walk repeats an edge, then it is not a circuit.
For example,
\[ a,b,a \]repeats \(\{a,b\}\) in an undirected graph.
Common Error: Counting Vertices Instead of Edges
The path
\[ a,b,c,d \]lists four vertices but uses only three edges.
Therefore its length is
\[ \boxed{3}, \]not \(4\).
Common Error: Assuming Visual Closeness Gives Connectivity
Vertices drawn near one another are not connected unless edges and paths actually join them.
Connectivity depends on graph structure, not on physical distance in the drawing.
Common Error: Reversing a Directed Path
In an undirected graph, a path can be traversed in reverse.
In a directed graph, the reverse sequence is valid only if the required reverse directed edges exist.
A Reliable Procedure for Classifying a Route
- Check that every consecutive pair of vertices is joined appropriately.
- If not, the sequence is not a walk.
- If it is a walk, check whether any edge repeats.
- If no edge repeats, it is a trail.
- Check whether any vertex repeats.
- If no vertex repeats, it is a path.
- Check whether the first and last vertices match.
- If a trail is closed, it is a circuit.
- If a closed route repeats no vertex except the start/end vertex, it is a cycle.
A Reliable Procedure for Checking Connectivity
- Choose a starting vertex.
- Follow edges to identify every vertex reachable from it.
- If every vertex is reachable, the undirected graph is connected.
- If some vertices are unreachable, the graph is disconnected.
- Repeat the process from an unreached vertex to identify another component.
- Continue until every vertex belongs to exactly one connected component.
Example: Full Route Classification
In the running graph, consider
\[ a,b,c,d,b. \]Every consecutive pair is adjacent, so it is a walk.
Its edges are
\[ \{a,b\},\{b,c\},\{c,d\},\{d,b\}. \]No edge repeats, so it is a trail.
The vertex \(b\) repeats, so it is not a path.
The starting and ending vertices differ, so it is not a circuit.
Example: Full Connectivity Workflow
Let
\[ V=\{1,2,3,4,5,6\} \]and
\[ E= \bigl\{ \{1,2\},\{2,3\},\{1,3\},\{4,5\} \bigr\}. \]Starting at \(1\), we can reach
\[ \{1,2,3\}. \]Starting at \(4\), we can reach
\[ \{4,5\}. \]Vertex \(6\) is isolated.
Therefore the graph has three connected components:
\[ \boxed{\{1,2,3\},\qquad\{4,5\},\qquad\{6\}}. \]Practice 1: Walk
In the running graph, determine whether
\[ a,b,c,d,e \]is a walk.
Practice 2: Trail
Determine whether
\[ a,b,c,a \]is a trail.
Practice 3: Path
Determine whether
\[ a,b,c,b,d \]is a path.
Practice 4: Circuit
Determine whether
\[ a,b,c,a \]is a circuit.
Practice 5: Length
Find the length of
\[ a,c,d,b,a. \]Practice 6: Reachability
In the running graph, give one path showing that \(e\) is reachable from \(a\).
Practice 7: Connected or Disconnected
Let
\[ V=\{p,q,r,s\} \]and
\[ E=\bigl\{\{p,q\},\{q,r\}\bigr\}. \]Is the graph connected?
Practice 8: Components
For the graph in Practice 7, list its connected components.
Practice 9: Directed Reachability
Suppose a digraph contains
\[ a\to b,\qquad b\to c,\qquad c\to d. \]Is \(d\) reachable from \(a\)? Is \(a\) necessarily reachable from \(d\)?
Practice 10: Identify the Error
A student says that
\[ a,b,c,b,d \]is a path because no edge repeats.
Explain the error.
Practice Answers
Practice 1
The consecutive pairs
\[ \{a,b\},\{b,c\},\{c,d\},\{d,e\} \]are all edges of the running graph. Therefore,
\[ \boxed{a,b,c,d,e\text{ is a walk}}. \]Practice 2
The route uses
\[ \{a,b\},\{b,c\},\{c,a\}, \]with no repeated edge. Therefore,
\[ \boxed{a,b,c,a\text{ is a trail}}. \]Practice 3
The vertex \(b\) appears twice.
Under our convention, a path cannot repeat a vertex. Therefore,
\[ \boxed{a,b,c,b,d\text{ is not a path}}. \]Practice 4
The route begins and ends at \(a\), and no edge repeats. Therefore,
\[ \boxed{a,b,c,a\text{ is a circuit}}. \]Practice 5
The route
\[ a,c,d,b,a \]traverses four edges. Therefore,
\[ \boxed{\text{length}=4}. \]Practice 6
One valid path is
\[ \boxed{a,b,d,e}. \]Practice 7
Vertex \(s\) is isolated, so no path connects \(s\) to \(p\), \(q\), or \(r\).
\[ \boxed{\text{The graph is disconnected.}} \]Practice 8
Vertices \(p,q,r\) form one connected component, while \(s\) forms a one-vertex component:
\[ \boxed{\{p,q,r\},\qquad\{s\}}. \]Practice 9
Following the arrows gives the directed path
\[ a\to b\to c\to d, \]so \(d\) is reachable from \(a\).
The reverse reachability is not guaranteed because reverse directed edges have not been given.
\[ \boxed{d\text{ is reachable from }a,\text{ but }a\text{ need not be reachable from }d}. \]Practice 10
The student has checked the condition for a trail, not the stronger condition for a path.
Since \(b\) repeats,
\[ \boxed{a,b,c,b,d\text{ is not a path}}. \]What to Remember
- A walk follows adjacent vertices and may repeat vertices and edges.
- A trail is a walk with no repeated edges.
- A path is a walk with no repeated vertices.
- A closed walk begins and ends at the same vertex.
- A circuit is a closed trail.
- A cycle repeats no vertex except the common start/end vertex.
- The length of a route is the number of edges traversed.
- A vertex is reachable from another if a path connects them.
- An undirected graph is connected when every pair of vertices is joined by a path.
- Connected components are the maximal connected pieces of a graph.
- Directed reachability must follow arrow direction.
Where We Go Next
Paths and connectivity describe how vertices can be linked through a graph. One especially important class of connected graphs contains no cycles at all.
The next lesson, Trees and Rooted Trees, studies these cycle-free connected structures and the hierarchical relationships they can represent.