Eulerian Trails and Circuits (Extension) Revision Notes for VCE SSCE General Mathematics

Eulerian Trails and Circuits (Extension)

Introduction

When studying graphs and networks, we sometimes need to find a path that travels along every edge exactly once. These special paths are called Eulerian trails and Eulerian circuits, named in honour of mathematician Leonhard Euler, who first studied these patterns in graph theory.

Understanding these concepts helps us solve practical problems, such as planning efficient delivery routes or inspecting road networks without having to travel the same path twice.

What is an Eulerian trail?

An Eulerian trail is a path through a graph that travels along each edge exactly once, without repeating any edge. Think of it as drawing the entire graph without lifting your pen and without going over the same line twice.

infoNote

The "pen drawing" analogy is helpful for visualizing Eulerian trails: imagine trying to trace the entire graph in one continuous motion, never lifting your pen and never retracing any line. If you can do this, the graph has an Eulerian trail!

Conditions for an Eulerian trail to exist

For a graph to have an Eulerian trail, it must meet two specific conditions:

The graph must be connected (all parts of the graph are linked together in one piece)
The graph must have exactly zero or two vertices with an odd degree

The degree of a vertex refers to the number of edges connected to that vertex.

Starting and ending points

The number of odd-degree vertices determines where the Eulerian trail can start and finish:

If there are zero odd vertices: The trail can start at any vertex and will return to the starting point
If there are two odd vertices: The trail must start at one odd vertex and will finish at the other odd vertex

What is an Eulerian circuit?

An Eulerian circuit is a special type of Eulerian trail that starts and finishes at the same vertex, forming a closed loop.

Conditions for an Eulerian circuit to exist

For a graph to have an Eulerian circuit, it must meet these conditions:

The graph must be connected
All vertices must have an even degree

When all vertices have an even degree, you can start your circuit at any vertex in the graph, and you will always be able to return to your starting point after travelling every edge exactly once.

chatImportant

Key Distinction: An Eulerian circuit is more restrictive than an Eulerian trail. While a trail only requires zero or two odd vertices, a circuit requires ALL vertices to have even degree. This means every Eulerian circuit is also an Eulerian trail, but not every Eulerian trail is an Eulerian circuit.

Identifying Eulerian trails and circuits

To determine whether a graph has an Eulerian trail, circuit, both, or neither, follow these steps:

Check if the graph is connected
Count the degree of each vertex
Identify how many vertices have an odd degree
Apply the rules:
- Zero odd vertices → Both an Eulerian trail and circuit exist
- Exactly two odd vertices → Only an Eulerian trail exists
- More than two odd vertices → Neither exists

lightbulbExample

Worked Example: Analysing three graphs

Let's examine three different graphs to determine their Eulerian properties.

Graph a:

Structure: A square with vertices $A$ , $B$ , $C$ , $D$ and both diagonals drawn
Degree analysis:
- Each vertex connects to all other vertices
- Each vertex has degree 4 (even)
Result: All vertices have even degree, so the graph has both an Eulerian trail and an Eulerian circuit
Example circuit: $A \to C \to B \to D \to A$

Graph b:

Structure: Vertices $A$ , $B$ , $C$ , $D$ , $E$ forming a connected network
Degree analysis:
- Vertices $E$ and $D$ have odd degree
- Remaining vertices ( $A$ , $B$ , $C$ ) have even degree
Result: Exactly two odd vertices, so the graph has an Eulerian trail but not an Eulerian circuit
Example trail: $E \to A \to D \to E \to B \to C \to D$
Note: The trail starts at one odd vertex ( $E$ ) and ends at the other odd vertex ( $D$ )

Graph c:

Structure: Vertices $A$ , $B$ , $C$ , $D$ , $E$ with multiple connections
Degree analysis:
- More than two vertices have odd degree
Result: More than two odd vertices, so the graph has neither an Eulerian trail nor an Eulerian circuit

Exam tip: When analysing a graph, systematically list the degree of each vertex. This organised approach helps you avoid mistakes and makes it easy to count odd-degree vertices.

Why are Eulerian trails and circuits important?

These concepts have significant practical applications in the real world. When a graph represents locations as vertices and paths as edges, finding an Eulerian trail or circuit helps us plan efficient routes.

Real-world applications

Understanding Eulerian trails and circuits helps solve problems such as:

Mail delivery: A postal worker wants to deliver mail along every street without travelling along any street more than once, minimising time and distance
Tourist route planning: A visitor to a tourist park wants to see all attractions by walking along every path exactly once, without retracing their steps
Road inspection: A road inspector needs to inspect all roads connecting country towns without having to travel along each road more than once, saving fuel and time
Snow ploughing: City maintenance crews can plan routes to clear all streets efficiently
Security patrols: Guards can plan routes that cover all areas without unnecessary repetition

In each case, the efficiency gained by not repeating paths saves time, money, and resources.

infoNote

Application Strategy: In application problems, first identify what the vertices and edges represent in the real-world context. Then determine whether an Eulerian trail or circuit would solve the problem, and check if the graph structure allows it.

bookmarkSummary

Key Points to Remember:

An Eulerian trail travels every edge exactly once; possible when a connected graph has zero or two odd-degree vertices
An Eulerian circuit is an Eulerian trail that starts and ends at the same vertex; possible when all vertices have even degree
Count vertex degrees systematically: zero or two odd vertices allow a trail, all even vertices allow a circuit
If two odd vertices exist, the Eulerian trail must start at one odd vertex and end at the other
These concepts solve practical routing problems where efficiency matters, such as mail delivery or road inspection

Eulerian Trails and Circuits (Extension) (VCE SSCE General Mathematics): Revision Notes