At a glance. One lesson of about 60 minutes. It builds on degree and the handshake result. Students apply the odd-vertex test, find Hamilton cycles by search, and count orders of vertices in a complete graph.
Calculator: no calculator. No calculator: degrees are small counts and the arrangements are products of 5, 4, 3, 2 and 1 that students write out.
What students will learn
Know
- An Euler circuit needs all degrees even; an Euler trail needs exactly two odd vertices.
- A Hamilton cycle visits every vertex exactly once and returns.
- A complete graph on n vertices has degree n − 1 at every vertex.
Understand
- Why the odd-vertex test works: passing through a vertex uses two edges, so the ends of a trail are the only odd vertices.
- Why there is no simple test for Hamilton cycles.
- Why a route and its reverse are one cycle.
Do
- Apply the odd-vertex test.
- Find or rule out a Hamilton cycle in a small graph.
- Count orders of the vertices with a fixed start.
MYP assessment criteria
Wording paraphrased. What this lesson gives you evidence for, and what to look for:
- Criterion A. Knowing and understanding: the definitions and the odd-vertex test (questions 1 to 8).
- Criterion B. Investigating patterns: the figure. Students compare the four networks and conjecture when each kind of route exists.
- Criterion C. Communicating: justifying that no Hamilton cycle exists by naming the vertex that would be visited twice.
- Criterion D. Applying mathematics in real-life contexts: deliveries, postal rounds and courier tours (hook and questions 2 and 5).
The one thing to do with the figure
Ask for the prediction first. Then move through the four networks and ask for the Euler verdict before the readout, and again for the Hamilton verdict.
Ask: “Which network has a Hamilton cycle but no Euler route, and which has an Euler circuit but no Hamilton cycle?” Networks 3 and 4.
A possible order
| 5 min | Warm-up from the student page, in silence, then answers. |
|---|---|
| 5 min | Hook: the seven bridges; collect predictions. |
| 12 min | Figure, key idea and warning card; ask for the Euler verdict before each readout. |
| 8 min | Worked examples; pairs finish the faded example. |
| 5 min | Question 1, the check. If many choose B, ask what must be true of every vertex for a circuit. |
| 20 min | Your turn, Levels 1 to 3, at each student's own pace. |
| 5 min | Something to think about, then the exit ticket, question 8. |
The answers
| Warm-up | 18; 6; no. |
|---|---|
| Hook | The four districts have degrees 5, 3, 3 and 3, so four vertices are odd and no route can cross every bridge exactly once. One bridge would have to be added or removed to leave two odd districts and allow a trail. |
| Worked examples | A trail but no circuit; P, Q, R, S, P; no Euler route. |
| Faded example | An Euler trail from P to Q, with 6 edges. |
| 1. Applying the odd-vertex test | A. B needs every degree even; C thinks two odd vertices forbid a trail; D starts at the largest degree. |
| 2. Counting odd vertices | 4. 3, 5, 3 and 1. |
| 3. Missing degree for a trail | 1. k odd, so 1. |
| 4. Complete graphs and Euler circuits | 4. n = 3, 5, 7, 9. |
| 5. Counting orders | 120. 5! |
| 6. Distinct Hamilton cycles | 360. 720 ÷ 2. |
| 7. Adding an edge | 4. 6 − 2. |
| 8. Euler without Hamilton | D. A has both, B is the reverse, C has a trail but no circuit. |
What each wrong answer tells you
| They give | What it usually means | What to do |
|---|---|---|
| B, C or D in question 1 | Wanted a circuit, thought odd vertices forbid any route, or started at the busiest junction. | Ask for the degree of each junction, then ask where a trail must start and end. |
| 8 or 28 in question 2 | Counted every junction, or added the degrees. | Ask the student to circle only the odd numbers and count the circles. |
| 2 or 3 in question 3 | Did not check that the sum must be even, or gave a valid but not smallest value. | Ask: what happens to the sum for k = 2? Then list the odd values in order. |
| 3 or 7 in question 4 | Counted the even values, or counted all the values. | Ask: what is the degree of each vertex in a complete graph on n vertices? |
| 720 or 25 in question 5 | Let the start move, or allowed a town to be chosen twice. | Write out the choices: 5 for the first town, 4 for the second, and so on. |
| 720 or 5040 in question 6 | Did not account for direction, or did not fix a start. | Write a cycle and its reverse and ask whether they are different. |
| 6 or 2 in question 7 | Gave the number before the change, or the number that changed. | Ask: which vertices change degree, and which ones stay at 3? |
| A, B or C in question 8 | Checked only the degrees, reversed the two ideas, or confused a trail with a circuit. | Ask for the degrees in each network, then try to draw a cycle through every vertex. |
Questions worth asking
- Why do the ends of a trail have odd degree? Listen for: every time the route passes through a vertex it uses one edge in and one out, so only the start and finish have an unpaired edge.
- Can a graph have an Euler circuit but no Hamilton cycle? Listen for: yes, two triangles meeting at a vertex.
- Why does a Hamilton cycle have no quick test? Listen for: nobody knows a quick rule, so we search or find a vertex that blocks it.
- Why divide by 2 when counting distinct cycles? Listen for: going round the other way gives the same cycle.
Differentiation
A way in for anyone stuck
- Give each student the four networks printed on one page with space to write degrees beside each vertex.
- Provide a table with columns for vertex, degree, odd or even, and a total row for the number of odd vertices.
- Give the frame: “There are … odd vertices, so there is an Euler ….”
Stretch
- Prove that a graph with exactly two odd vertices has an Euler trail that must start at one of them.
- How many Euler circuits does the pentagon with a chord at every vertex (the complete graph on 5 vertices) have? Why is it hard to count them?
Students learning in English as an additional language
“Route” means a way to go along edges. “Circuit” and “cycle” both mean a route that returns to its start. “Trail” means it ends somewhere else. “Visit” means to arrive at a vertex.
| Word | Plain meaning | Example |
|---|---|---|
| Euler circuit | a route that uses every edge once and returns to its start | a postal round |
| Euler trail | a route that uses every edge once and ends elsewhere | start at one odd vertex |
| Hamilton cycle | a route that visits every vertex once and returns | a tour of every town |
| connected | every vertex can be reached from every other | a road map with no island |
| complete graph | every pair of vertices is joined by an edge | every town has a road to every other |
Sentence starters for explaining aloud or in writing:
- There are … odd vertices, so …
- A Hamilton cycle exists because the order … visits every vertex once.
- There is no Hamilton cycle because … would have to be visited twice.
Two things not to say
“Euler and Hamilton are the same thing.” Say instead: Euler routes are about edges and Hamilton routes are about vertices.
“A graph with even degrees is always possible to tour.” Say instead: even degrees guarantee an edge-covering circuit, and nothing about visiting every vertex once.
Questions to set
Extra practice in three tiers, including one question from earlier work for spacing. Every answer has been checked.
1Fluency
The idea on its own, with friendly numbers. Set these first.
- FindA graph has degrees 4, 4, 2, 2, 2. Does it have an Euler circuit?
Yes. Every degree is even. - FindA graph has degrees 3, 3, 3, 3. Does it have an Euler route?
No. Four odd vertices.
2In context
The same idea inside a situation, where the first job is deciding what to calculate.
- ContextA street map has two junctions with an odd number of streets and all others even. Where must a street-sweeper start and finish?
At the two odd junctions, one at each end. - Earlier work (lesson 1)A graph has 8 vertices and every vertex has degree 3. How many edges?
12.
3Challenge
Reasoning, generalizing and working backwards.
- ReasoningThe graph K(2,3) has two vertices of degree 3 and three of degree 2. Has it a Hamilton cycle?
No. A cycle alternates between the two sets, so it needs equal numbers in each. - Working backwardsA complete graph has 15 edges. How many vertices, and does it have an Euler circuit?
6 vertices (6 × 5 ÷ 2 = 15). Degree 5 is odd, so no.
Practicalities
Works on a phone or a shared screen. Nothing a student types is saved or sent anywhere.
The figure works with the keyboard (tab to the slider, then the arrow keys) and by touch. “Show me the steps” gives the same states in words.
No calculator is needed.