Walks, trails, paths, cycles and circuits
Exploring and travelling involves moving between vertices along the edges of a graph. Understanding the various methods and mathematical principles behind this allows for the identification of the most efficient routes and ways to optimise resources such as time, distance, and cost.
Use this page to revise the following concepts within walks, trails, paths, cycles and circuits:
Basic Terminology
Some of the key terminology required for understanding exploring and travelling problems include:
The trail \(B-D-E-B-C-E-B\) can be considered a circuit as it starts and ends at \(B\), with no 
The path \(B-D-E-C-B\) can be considered a cycle as it starts and ends \(B\), with no
Check your understanding
View
Eulerian Trails and Circuits
Eulerian trails and circuits describe a trail or circuit that traverses every edge of a graph once. They can only occur on connected graphs.
Eulerian Trail
Eulerian trails can start at any vertex and end at any other vertex. These exist on a graph when it has exactly two vertices with an odd degree. The two vertices with an odd degree indicate the starting or ending vertex.
This can be observed in how a walk passes through a vertex with different degrees.
Consider a vertex with an even degree:
If the vertex has an even degree, the trail must pass through it.
Consider a vertex with an odd degree:
If the vertex has an odd degree, there must be a trail either starting or terminating at that vertex. Any additional even component would be the trail passing through the vertex.
Worked Example
Determine whether the graph below contains a Eulerian trail. If it does, provide one of the trails.
Determine the degree of each of the vertices
\(\deg(A)=1,\ \deg(B)=4,\ \deg(C)=2,\ \deg (D)=2,\ \deg (E )=3\)
There are two vertices with an odd degree (\(A\) and \(E\)) therefore a Eulerian trail exists, and begins and starts at \(A\) or \(E\).
Draw on the graph physically or mentally to determine the trail
A possible Eulerian trail is \(A-B-C-E-D-E\).
NoteThis is not the only Eulerian trail. Starting at E is also an option. For example \(E-B-C-E-D-B-A\) is also a valid Eulerian trail. |
Check your understanding
View
Eulerian Circuit
Eulerian circuits must start and end on the same vertex. As it starts and ends on the same vertex, this vertex must be even. Therefore, Eulerian circuits only exist on a graph when it has all vertices with an even degree. Starting and ending can occur at any vertex to create a Eulerian circuit.
Worked Example
Determine whether the graph below contains a Eulerian circuit. If it does, provide one of the circuits.
Determine the degree of each of the vertices
\(\deg(A)=2,\ \deg(B)=4,\ \deg(C)=2,\ \deg(D)=4,\ \deg(E )=4\)
All of the vertices have an even degree. Therefore, Eulerian circuits exist in this graph.
Draw on the graph physically or mentally to determine the trail
A possible Eulerian trail is \(A-B-C-E-D-E-B-D-A\).
NoteThis is also not the only Eulerian circuit. It can start from any vertex, and can traverse multiple ways. |
Check your understanding
View
Hamiltonian Paths and Cycles
Hamiltonian paths and cycles describe paths or cycles that traverse every vertex of a graph only once. As these are paths, edges cannot be repeated as well ; however not every edge needs to be traversed.
- Hamiltonian paths must start at one vertex and end at another.
- Hamiltonian cycles must start and end at the same vertex.
There are no straightforward methods of determining exact solutions for these. As a result, simpler Hamiltonian path and cycle problems are solved by inspection or trial-and-error.