Worked examples
The question
Question: find an Euler path in the graph AB, BC, AC.
edges: AB, BC, AC
1 Draw the graph
Each letter is a vertex: a dot.
Each pair is an edge: a line between two vertices.
An Euler path uses every edge exactly once.
An Euler circuit also ends where it started.
Euler path: every edge once
Euler circuit: and back to the start
2 Count the degrees
The degree of a vertex is how many edges touch it.
A has 2.
B has 2.
And so on.
3 Add the degrees
Add the degrees: 6.
That is 2 times the 3 edges, because each edge has two ends.
It always works: the handshake rule.
2 + 2 + 2 = 6 = 2 × 3 edges
4 Find the odd vertices
The rule: each time we pass through a vertex we use two of its edges, one in and one out.
So only the start and the end can be odd.
0 odd: circuit (start anywhere)
2 odd: path from one odd to the other
more: no Euler path
Careful!
With no odd vertices we can start anywhere, and we come back to the start.
Careful: a circuit ends where it started
5 Walk the route
Start at A.
Go to B: edge 1.
Last, C to A: edge 3.
The circuit: A, B, C, A.
= circuit: A, B, C, A
6 Check
Check: every edge has exactly one number, 1 to 3, and there are 3 edges.
Right!
numbers 1 to 3, 3 edges: each used once
Let's look back.
First: draw the graph.
Then: count the degrees.
Then: add the degrees.
Then: find the odd vertices.
Then: walk the route.
Last: check.
Answer = circuit: A, B, C, A
▶ Watch it solved
The question
Question: find an Euler path in the graph AB, AC, AD, BC, CD.
edges: AB, AC, AD, BC, CD
1 Draw the graph
Each letter is a vertex: a dot.
Each pair is an edge: a line between two vertices.
An Euler path uses every edge exactly once.
An Euler circuit also ends where it started.
Euler path: every edge once
Euler circuit: and back to the start
2 Count the degrees
The degree of a vertex is how many edges touch it.
A has 3.
B has 2.
And so on.
3 Add the degrees
Add the degrees: 10.
That is 2 times the 5 edges, because each edge has two ends.
It always works: the handshake rule.
3 + 2 + 3 + 2 = 10 = 2 × 5 edges
4 Find the odd vertices
Ring the vertices with an odd degree: A and C.
The rule: each time we pass through a vertex we use two of its edges, one in and one out.
So only the start and the end can be odd.
0 odd: circuit (start anywhere)
2 odd: path from one odd to the other
more: no Euler path
Careful!
If we start at an even vertex, we get stuck before the end.
Start at one odd vertex, end at the other.
Careful: not start at B ✗
5 Walk the route
Start at A, an odd vertex.
Go to B: edge 1.
Last, D to C: edge 5.
The path: A, B, C, A, D, C.
= path: A, B, C, A, D, C
6 Check
Check: every edge has exactly one number, 1 to 5, and there are 5 edges.
Right!
numbers 1 to 5, 5 edges: each used once
Let's look back.
First: draw the graph.
Then: count the degrees.
Then: add the degrees.
Then: find the odd vertices.
Then: walk the route.
Last: check.
Answer = path: A, B, C, A, D, C
▶ Watch it solved
The question
Question: find an Euler path in the graph AB, AC, AD, BC, BD, CD, DE, CE.
edges: AB, AC, AD, BC, BD, CD, DE, CE
1 Draw the graph
Each letter is a vertex: a dot.
Each pair is an edge: a line between two vertices.
An Euler path uses every edge exactly once.
An Euler circuit also ends where it started.
Euler path: every edge once
Euler circuit: and back to the start
2 Count the degrees
The degree of a vertex is how many edges touch it.
A has 3.
B has 3.
And so on.
3 Add the degrees
Add the degrees: 16.
That is 2 times the 8 edges, because each edge has two ends.
It always works: the handshake rule.
3 + 3 + 4 + 4 + 2 = 16 = 2 × 8 edges
4 Find the odd vertices
Ring the vertices with an odd degree: A and B.
The rule: each time we pass through a vertex we use two of its edges, one in and one out.
So only the start and the end can be odd.
0 odd: circuit (start anywhere)
2 odd: path from one odd to the other
more: no Euler path
Careful!
If we start at an even vertex, we get stuck before the end.
Start at one odd vertex, end at the other.
Careful: not start at C ✗
5 Walk the route
Start at A, an odd vertex.
Go to B: edge 1.
Last, D to B: edge 8.
The path: A, B, C, A, D, C, E, D, B.
= path: A, B, C, A, D, C, E, D, B
6 Check
Check: every edge has exactly one number, 1 to 8, and there are 8 edges.
Right!
numbers 1 to 8, 8 edges: each used once
Let's look back.
First: draw the graph.
Then: count the degrees.
Then: add the degrees.
Then: find the odd vertices.
Then: walk the route.
Last: check.
Answer = path: A, B, C, A, D, C, E, D, B
▶ Watch it solved
