Traversals and Circuits (AI HL)
Some routes through a graph must use every edge; others must visit every vertex. Telling these two ideas apart - and knowing the degree conditions that decide whether such a route even exists - is the core skill this sub-topic tests. It's part of the broader Graph Theory topic.
15 questions on this sub-topic.
Eulerian and Hamiltonian routes
Covered under IB syllabus reference AHL3.14: graphs, degree of a vertex, and the subgraphs and trees built from them.
Eulerian circuits
A closed route using every edge exactly once (an Eulerian circuit) exists only if every vertex has even degree. If exactly two vertices are odd, an Eulerian trail (not a closed circuit) exists between them.
Not in the formula booklet - existence conditionHamiltonian cycles
A Hamiltonian cycle visits every vertex exactly once and returns to the start - the opposite focus to an Eulerian circuit, which is about edges.
Not in the formula booklet - there's no simple degree test like the Eulerian one. The nearest-neighbour algorithm gives an achievable upper bound on the shortest such cycle, not a guarantee of the optimal one.
Want the full syllabus wording and the travelling salesman bound algorithms? See Graph Theory.
Worked examples
A graph G has an Eulerian circuit. A new edge is added between two distinct vertices that are already in G.
(a) What happens to the degrees of those two vertices?
(b) Does the modified graph necessarily still have an Eulerian circuit?
Worked solution
(a) Each of the two vertices gains 1 to its degree M1
- both previously even degrees become odd. A1
(b) No - the two newly odd-degree vertices mean the graph has exactly two odd-degree vertices, so it has an Eulerian trail (not a circuit) between those two vertices. A1
Consider a connected graph.
(a) State the condition for a connected graph to have an Eulerian circuit.
(b) A graph has vertex degrees \(2, 2, 3, 3, 4.\) Determine whether it has an Eulerian circuit, an Eulerian path, or neither.
Worked solution
(a) A connected graph has an Eulerian circuit iff every vertex has even degree. M1 A1
(b) Exactly two vertices have odd degree (the two of degree 3), M1 A1
there is an Eulerian path (not a circuit). A1
Common mistakes
- Assuming any pair of odd-degree vertices gives a circuit. Exactly two odd vertices means an Eulerian trail exists between them - it does not close back into a circuit unless every vertex is even degree.
- Mixing up edge-based and vertex-based conditions. An Eulerian circuit is about using every edge once (tested by vertex degree); a Hamiltonian cycle is about visiting every vertex once. They test different things and have different existence tests.
- Treating nearest-neighbour as the optimal tour. The nearest-neighbour algorithm only produces an achievable upper bound for the travelling salesman problem - a shorter tour may still exist.
Ready to practise properly?
16 traversal and circuit questions, marked instantly like the real exam.
Quick answers
When does a graph have an Eulerian circuit?
A connected graph has an Eulerian circuit - a closed route using every edge exactly once - if and only if every vertex has even degree.
What is the difference between an Eulerian trail and an Eulerian circuit?
Both use every edge exactly once. A circuit returns to its starting vertex and needs all vertices to have even degree; a trail does not return to the start and needs exactly two odd-degree vertices, which become the endpoints.