In the Bridges of Königsberg problem, we were trying to find a route that used every edge exactly once.
Graph theory has names for different kinds of routes through a graph.
Routes through a graph
Consider the following graph:
💡
A path follows edges of a graph without visiting the same vertex twice.
Example: A → B → C → D
A cycle returns to its starting vertex, without repeating any other vertex.
Example: A → B → C → A
A trail follows edges without using the same edge twice. It may visit the same vertex more than once.
Example: C → A → B → C → D → E
An Eulerian path is a trail that uses every edge of the graph exactly once. It does not have to finish where it started.
Example: C → A → B → C → D → E → F → D
An Euler circuit uses every edge exactly once and returns to the vertex where it started. In other words, it is an Eulerian path that finishes at the same vertex where it started.
The graph above has an Eulerian path, but not an Euler circuit.
Example on a different graph: A → B → C → D → A
What type of route is it?
Here are three routes on the same graph. Look at the highlighted edges and decide every description that applies to each route. A route may be more than one thing — for example, it might be both a path and a trail.
Route 1
A → B → C → D
Route 2
A → B → C → D → E → A
Route 3
A → B → C → D → E → A → C
Build a route
Click any vertex to choose where to start. Then click a connected vertex to travel along an edge. Your route will be highlighted as you go.
💡
The degree rule
In the previous lesson, we discovered that odd and even degrees tell us whether an Eulerian path is possible.
For a connected graph — meaning you can get from any vertex to any other vertex by following edges:
- Zero odd-degree vertices → the graph has an Euler circuit.
- Two odd-degree vertices → the graph has an Eulerian path, but not an Euler circuit.
- More than two odd-degree vertices → the graph has no Eulerian path.
Does the degree list determine the graph?
These two graphs have the same degree sequence: 2, 2, 2, 1, 1. But are they actually the same kind of graph?
What is different about the two graphs, even though their degree lists are identical?
Reveal answer
Graph A is connected: you can travel between any two vertices by following edges.
Graph B is disconnected: the triangle and the separate edge form two different pieces.
So a degree sequence tells us how many edges meet each vertex, but it does not tell us exactly how those vertices are joined. Different graphs can have the same degree sequence.
Practice puzzles
Puzzle 1 – Use the rule
A connected graph has vertex degrees:
4, 2, 2, 2, 2
Without drawing the graph, decide:
- Does it have an Eulerian path?
- Does it have an Euler circuit?
Hint: How many vertices have odd degree?
Reveal answer
All five degrees are even, so there are 0 odd-degree vertices.
Therefore the graph has an Euler circuit — and hence also an Eulerian path.
Puzzle 2 – Use the rule
A connected graph has vertex degrees:
4, 3, 2, 2, 1
Without drawing the graph, decide:
- Does it have an Eulerian path?
- Does it have an Euler circuit?
- Where must the trail start and finish?
Reveal answer
There are exactly two odd-degree vertices: 3 and 1.
So the graph has an Eulerian path, but not an Euler circuit.
The trail must start at one odd-degree vertex and finish at the other.
How could the start and finish instead have even degree?
Hint: What changes if you finish at the same vertex where you started?
Reveal answer
If the start and finish are the same vertex, the edges there can also be paired: each time you leave, you eventually come back.
Then every vertex can have even degree. The trail returns to where it began, so it is an Euler circuit.
Puzzle 3 – What happens with four odd vertices?
A connected graph has degrees:
3, 3, 2, 2, 1 and 1
Without drawing the graph, decide:
- Does it have an Eulerian path?
- Does it have an Euler circuit?
- What feature of the degree list tells you immediately?
Reveal answer
There are four odd-degree vertices: 3,3,1 and 1.
An Eulerian path is possible only when there are zero or two odd-degree vertices.
So the graph has no Eulerian path and therefore no Euler circuit.
You do not need to know what the graph looks like — counting the odd-degree vertices is enough.
Repair the graph
💡
This graph has four odd-degree vertices, so it does not have an Eulerian path.
Add exactly one new edge so that an Eulerian path becomes possible.
Click one vertex, then another vertex to join them.
In the next lesson, we’ll use these ideas on a classic type of puzzle:
Can you draw a picture without lifting your pencil or drawing any line twice?
Download the printable lesson materials and supplementary examples for Paths, Cycles and Euler Trails.
Find the resources →