Traversing a Graph Revision Notes for AQA A-Level Further Maths

Traversing a Graph

Introduction to graph traversal

When working with graphs in mathematics, we often need to move around them by following edges from one vertex to another. This movement is called traversing the graph. Understanding the different ways we can traverse a graph is essential for solving many practical problems in network theory.

infoNote

A journey through a graph where you can repeat edges and vertices as many times as you want is called a walk.

Types of walks

Different restrictions on how we move through a graph create different types of journeys. Each type has a specific name and properties.

Walk

Definition: A walk is any continuous journey around a graph where there are no restrictions on repeating edges or vertices.

You can travel along any edge and visit any vertex multiple times. This is the most general type of movement through a graph.

Trail

Definition: A trail is a walk where no edge is repeated.

In a trail, you can visit vertices more than once, but you cannot use the same edge twice. If a trail returns to its starting vertex, it is called a closed trail.

Path

Definition: A path is a walk where no edges or vertices are repeated (except you may return to the starting vertex).

A path represents the most efficient way to move through a graph without revisiting any location. If a path forms a closed loop back to the start, it is called a cycle.

Cycle

Definition: A cycle is a closed path that starts and ends at the same vertex without repeating any edges or vertices along the way.

infoNote

The diagram above shows examples of each type:

Walk (ABCFBCD): Vertices B and C are visited twice
Trail (ABCDEBF): Edge BF is used, then vertex B is visited again via different edges
Path (ABCFE): No vertices or edges repeated
Cycle (ABEFCA): Closed path returning to start vertex A

Always check carefully whether vertices or edges are repeated when classifying a route through a graph.

Special types of graphs

Tree

Definition: A tree is a connected graph with no cycles.

Trees are important structures in graph theory. They represent the minimal way to connect all vertices without creating any loops.

Hamiltonian cycle and graph

Definition: A Hamiltonian cycle is a cycle that visits every vertex in the graph exactly once.

A Hamiltonian cycle is sometimes called a Hamiltonian tour.

Definition: A Hamiltonian graph is a graph that contains a Hamiltonian cycle.

Example: The cycle ABCDEF in a hexagonal graph where each vertex is visited exactly once is a Hamiltonian cycle.

infoNote

For a cycle to be Hamiltonian, it must visit ALL vertices in the graph exactly once. Check you haven't missed any vertices.

Eulerian and semi-Eulerian graphs

One of the most important questions in graph theory is whether you can traverse a graph without lifting your pencil from the paper. This leads to the concepts of Eulerian and semi-Eulerian graphs.

Traversable (Eulerian) graphs

Definition: A graph is traversable or Eulerian if you can draw it by starting and finishing at the same point without lifting your pencil or going over any edge twice.

The route that traverses an Eulerian graph is called an Eulerian trail. For example, in a graph where ABCABCA forms a closed route using each edge once, ABCABCA is an Eulerian trail.

chatImportant

Key rule: A graph is Eulerian if and only if all vertices have even degree.

The degree of a vertex is the number of edges connected to it. When every vertex has an even degree, you can always find a route that starts and finishes at the same vertex while using each edge exactly once.

infoNote

Eulerian is pronounced "oi-leerie-ann", named after the mathematician Leonhard Euler who studied such graphs in the 18th century.

Semi-traversable (semi-Eulerian) graphs

Definition: A graph is semi-traversable or semi-Eulerian if it can only be drawn by starting and finishing at different points.

chatImportant

Key rule: A graph is semi-Eulerian if and only if it has exactly two vertices with odd degree.

The two odd degree vertices must be the start and finish points of your trail. You must begin at one odd vertex and end at the other.

Non-traversable (non-Eulerian) graphs

Definition: A graph is non-traversable or non-Eulerian if it cannot be drawn without lifting your pencil.

chatImportant

Key rule: A graph with more than two vertices of odd degree is non-Eulerian.

If a graph has four, six, or any other number greater than two of odd degree vertices, it is impossible to traverse it without either lifting your pencil or repeating an edge.

Understanding vertex degrees

The handshaking lemma tells us that the sum of all vertex degrees equals twice the number of edges in the graph. This means the total of all degrees must be an even number.

chatImportant

Key result: The number of vertices with odd degree in any graph must be even.

This is because the sum of degrees is even (equals $2 \times \text{number of edges}$ ), so there must be an even number of odd values in the sum.

This explains why:

Eulerian graphs have zero odd vertices (even number)
Semi-Eulerian graphs have exactly two odd vertices (even number)
Non-Eulerian graphs have four, six, eight, etc. odd vertices (even number)

You can never have one, three, five, or any odd number of odd degree vertices.

infoNote

Always count the degree of each vertex systematically. List them clearly: $A(2)$ , $B(3)$ , $C(4)$ , etc. Then identify which are odd.

If you find exactly zero odd vertices → Eulerian
Exactly two odd vertices → semi-Eulerian
More than two odd vertices → non-Eulerian

Worked examples

lightbulbExample

Worked Example 1: Analysing a graph

Consider a graph with eight vertices A, B, C, D, E, F, G, H where the degrees are: $A(2)$ , $B(3)$ , $C(4)$ , $D(3)$ , $E(4)$ , $F(4)$ , $G(4)$ , $H(2)$

a) Show that this graph is Hamiltonian.

One possible Hamiltonian cycle is AECGHDBA. This visits all eight vertices exactly once and returns to the start, so the graph is Hamiltonian.

b) Show that the graph is semi-Eulerian. Where would a trail start and finish?

First, identify vertices with odd degree:

B has degree 3 (odd)
D has degree 3 (odd)
All other vertices have even degree

There are exactly two vertices with odd degree, so the graph is semi-Eulerian.

The trail must start at one odd vertex and end at the other. Therefore, the trail would start at B and end at D, or start at D and end at B.

c) Modify the graph to make it Eulerian.

To make the graph Eulerian, all vertices must have even degree. Currently B and D both have degree 3.

If we add an edge between B and D, both vertices would then have degree 4 (even). All vertices would have even degree, making the graph Eulerian.

lightbulbExample

Worked Example 2: The rooms and doors problem

A building has five rooms (A, B, C, D, E) and two doors to the outside. A prize is offered to anyone who can enter the building, pass through every door exactly once, and return to the outside.

Step 1: Model the situation as a graph

Represent each room as a vertex and each door as an edge connecting the rooms or the outside.

Step 2: Determine what type of traversal is needed

To win the prize, you must traverse the graph (use every edge exactly once). This requires an Eulerian trail.

Step 3: Calculate the degree of each vertex

From the floor plan:

Outside: degree 2
A: degree 2
B: degree 3
C: degree 2
D: degree 2
E: degree 5

Step 4: Identify odd degree vertices

Vertices with odd degree: B (degree 3) and E (degree 5)

There are exactly two vertices with odd degree.

Step 5: Determine if the graph is Eulerian

Since there are two odd degree vertices (not zero), the graph is semi-Eulerian, not Eulerian.

Conclusion: There is no prize-winning solution. You cannot start outside, pass through every door once, and return to the outside. You could only do this if you started at B (or E) and finished at E (or B).

This type of problem is called a circulation graph.

infoNote

In problems involving rooms and doors, always check whether you need to return to the starting point (Eulerian) or can finish elsewhere (semi-Eulerian). Read the question carefully.

bookmarkSummary

Key Points to Remember:

A walk allows repeated edges and vertices, a trail allows repeated vertices but not edges, a path allows no repetitions, and a cycle is a closed path.
A graph is Eulerian if all vertices have even degree, meaning you can traverse it starting and finishing at the same point.
A graph is semi-Eulerian if exactly two vertices have odd degree, meaning you must start at one odd vertex and finish at the other.
The number of odd degree vertices in any graph is always even (consequence of the handshaking lemma).
To classify a graph, list each vertex with its degree in brackets, identify which are odd, then apply the rules: zero odd → Eulerian, two odd → semi-Eulerian, more than two odd → non-Eulerian.

Traversing a Graph (AQA A-Level Further Maths): Revision Notes