What you’ll work on
- Graphs and networks
- Exploring and travelling problems
- Shortest path problems
Start with the idea
An Euler trail uses each edge once; a Hamiltonian path visits each vertex once. These answer different travel questions.
In a connected undirected graph, an Euler circuit requires all vertex degrees even; an open Euler trail has exactly two odd vertices. Dijkstra’s algorithm finds shortest routes with non-negative weights.
A worked example
A connected undirected graph has degrees 2, 2, 3, 3. Does it have an Euler trail or circuit?
- Exactly two vertices have odd degree
- these are the trail endpoints.
Answer: An open Euler trail, no Euler circuit.
Try one question
A connected undirected graph has degrees 4, 2, 2, 2, 2. What Euler traversal exists?
Show answer and explanation
An Euler circuit.
All degrees are even and the graph is connected.
Inside the collection
| Resource | Length | Practice | Answers |
|---|---|---|---|
| Learn and practise | 4 pages | 4 questions | Included |
| Apply and extend | 4 pages | 4 questions | Included |
| Topic checkpoint | 3 pages | 4 questions | Included |
Read on a device and work in an exercise book, or print the A4 PDFs. These files are not auto-marked digital quizzes.