Warm-up
Three quick ones from earlier work. Try each in your head or on paper before you open the answer.
- From lesson 1: a graph has 9 edges. What do its degrees add to?
Answer
18. Each edge is counted at both ends. - From Year 9: in how many different orders can 3 books be put in a row?
Answer
6. 3 × 2 × 1. - From lesson 1: could a graph have exactly three vertices of odd degree?
Answer
No. The number of odd vertices is always even.
Words used in this lesson
- Euler circuit
- a route that uses every edge once and returns to its start. For example: a postal round.
- Euler trail
- a route that uses every edge once and ends elsewhere. For example: start at one odd vertex.
- Hamilton cycle
- a route that visits every vertex once and returns. For example: a tour of every town.
- connected
- every vertex can be reached from every other. For example: a road map with no island.
- complete graph
- every pair of vertices is joined by an edge. For example: every town has a road to every other.
Can the van cross every bridge exactly once?
A market town in Peru has four districts, P, Q, R and S, separated by rivers. Two bridges join P and Q, two join P and R, and one bridge joins each of the pairs P and S, Q and S, and R and S: seven bridges in all. The council wants a van to cross every bridge exactly once on a market-day round. Treat each district as a vertex and each bridge as an edge, and the question becomes one about a graph. A route that uses every edge exactly once is an Euler route. If it ends where it began it is an Euler circuit; if it ends elsewhere it is an Euler trail.
Predict first: can the van cross every bridge exactly once? Then explore the four networks in the figure, and look at whether a route that visits every vertex once (a Hamilton route) behaves the same way.
Network 2: 2 vertices have odd degree, so there is an Euler trail between the two odd vertices; a Hamilton cycle exists.
Show me the steps
- Network 1, the pentagon: every degree is 2, so there is an Euler circuit, and going round the five sides is also a Hamilton cycle.
- Network 2, the pentagon with chord AC: A and C have degree 3, so there is an Euler trail that starts at one of them and ends at the other, and the sides still give a Hamilton cycle.
- Network 3, the pentagon with chords AC, BD and CE: four vertices have odd degree, so there is no Euler route at all, yet the sides are still a Hamilton cycle.
- Network 4, two triangles meeting at C: every degree is even, so there is an Euler circuit, but C would have to be visited twice to cover the other four vertices, so there is no Hamilton cycle.
Euler test, by counting odd vertices. A connected graph has an Euler circuit if every vertex has even degree, an Euler trail (starting at one odd vertex and ending at the other) if exactly two have odd degree, and no Euler route if more than two have odd degree.
Hamilton routes have no such test. A Hamilton cycle visits every vertex exactly once and returns. You find one by searching, or show there is none by finding a vertex that every cycle would have to pass through twice. A complete graph has a Hamilton cycle for every n of 3 or more; counting them is a counting problem: fix a start, then count the orders of the other vertices.
Two common slips. Thinking the two kinds of route go together: a network can have an Euler circuit and no Hamilton cycle, and the reverse. And using the odd-vertex count when the graph is not connected: if some part cannot be reached from another, no route can use every edge at all.
Worked examples
1. A postal worker must walk every street of a district once. The junction degrees are 2, 2, 3, 3 and 2. Is a round that returns to the depot possible?
- Two junctions have odd degree (the two with degree 3) and the other three are even.
- That gives an Euler trail but no circuit, so the walk can use every street once but cannot return to its start: it begins at one degree-3 junction and ends at the other.
2. Does the graph with edges PQ, QR, RS, SP and PR have a Hamilton cycle?
- Try going round the outside: P to Q to R to S and back to P.
- Every step uses an edge (PQ, QR, RS, SP), and every vertex is visited once, so yes: P, Q, R, S, P.
3. Does a complete graph with 6 vertices have an Euler circuit?
- Each vertex is joined to the 5 others, so every degree is 5, which is odd.
- All six vertices are odd, so there is no Euler route at all.
Your go. The first step is given. A graph has two vertices P and Q of degree 3 and three vertices R, S and T of degree 2. Decide whether it has an Euler circuit, an Euler trail or neither.
- Count the vertices with odd degree: P and Q.
- Use the test: how many odd vertices are there, and what does that number allow?
Check the answer
Two vertices have odd degree, so there is an Euler trail, from P to Q (or from Q to P), and no circuit. The sum of the degrees is 3 + 3 + 2 + 2 + 2 = 12, so there are 6 edges.
Check before you go on
1. A park has paths AB, BC, CA, CD, DE, EC and BD between five junctions. A gardener wants to walk along every path exactly once. Is it possible, and if so, where must she start?
Your turn
Start at Level 1 and go as far as you can. Type negative numbers with a minus sign, for example -7. A wrong answer gets a reason, not just a cross: read it, then try again.
Level 1 · Getting started
2. A delivery rider in Quito has a street map with eight junctions whose degrees are 3, 5, 4, 2, 4, 3, 6 and 1. How many junctions have odd degree?
3. A connected graph has five vertices with degrees 2, 4, k, 2 and 3, where k is a positive whole number. What is the smallest value of k for which the graph has an Euler trail but no Euler circuit?
Level 2 · Building
4. For how many values of n from 3 to 9 does the complete graph on n vertices have an Euler circuit?
5. A courier must start at town A, visit each of the other 5 towns exactly once, and return to A, and every pair of towns has a direct road. How many different orders of the 5 other towns are there, counting a route and its reverse as different?
Level 3 · Stretch
6. In the complete graph on 7 vertices, how many different Hamilton cycles are there if a cycle and the same cycle taken in the opposite direction count as one cycle?
7. A graph has 6 vertices and every vertex has degree 3. One new edge is added between two vertices that were not joined before. How many vertices now have odd degree?
Something to think about
A complete graph on n vertices has an Euler circuit when n is odd. For which n does it also have a Hamilton cycle, and does that depend on n being odd?
One way to think about it
For every n of 3 or more, because the vertices can be taken in any order and every pair is joined. So the Hamilton cycle does not depend on n being odd, while the Euler circuit does: degree n − 1 is even only when n is odd.
Exit ticket
8. Which graph has an Euler circuit but no Hamilton cycle?