Paths, Walks, Trails and Circuits
Brisbane's CityCycle bike-share maintenance crews need to inspect every dock without retracing any segment — that's an Eulerian trail problem. Whether a such a route exists depends entirely on counting odd-degree vertices. This lesson distinguishes walks, trails and paths, then gives you the rule for Eulerian circuits.
Practise this lesson
Three printable worksheets that build from foundations to mastery — or build your own from any module’s questions.
A postman must walk every street in a suburb exactly once and return to the post office. What conditions must the street network satisfy for this to be possible?
Before reading on — write your gut answer.
An Eulerian circuit exists if and only if every vertex has even degree and the network is connected. An Eulerian trail (not a circuit) exists iff exactly 2 vertices have odd degree.
Walk: any sequence of vertices/edges — can repeat vertices and edges.
Trail: walk with no repeated edges (vertices may repeat).
Path: walk with no repeated vertices (and therefore no repeated edges).
Circuit / Cycle: closed walk (starts and ends at same vertex). Eulerian circuit uses every edge exactly once.
Key facts
- Definitions: walk, trail, path, circuit
- Eulerian circuit: 0 odd-degree vertices
- Eulerian trail: exactly 2 odd-degree vertices
Concepts
- Why even degree allows circuit
- Difference between Eulerian and Hamiltonian
- When a postman problem is solvable
Skills
- Classify walk/trail/path in a network
- Check Eulerian circuit existence
- Find Hamiltonian path by inspection
Consider a network with vertices A, B, C, D and edges A–B, B–C, C–D, D–A, B–D.
- Walk A→B→D→B→C: visits B twice and uses edge B–D, then B–C. Valid walk — no restrictions on repetition.
- Trail A→B→C→D→A: no repeated edges — valid trail. Also a circuit (returns to start).
- Path A→B→C→D: no repeated vertices — valid path.
- A→B→D→A→B is a walk but NOT a trail (edge A–B repeated).
What to write in your book
- Walk: any sequence — can repeat vertices and edges.
- Trail: no repeated edges. Path: no repeated vertices.
- Circuit/Cycle: closed walk (returns to start vertex).
An Eulerian circuit uses every edge exactly once and returns to the start. It exists if and only if:
- The network is connected (all vertices reachable), AND
- Every vertex has even degree (0 odd-degree vertices).
An Eulerian trail (uses every edge once, different start and end) exists iff:
- The network is connected, AND
- Exactly 2 vertices have odd degree. (Start and end at those two vertices.)
What to write in your book
- Eulerian circuit: connected + all even degrees.
- Eulerian trail: connected + exactly 2 odd-degree vertices.
- Count odd-degree vertices to determine which (if any) exists.
A Hamiltonian path visits every vertex exactly once (different start and end). A Hamiltonian cycle visits every vertex exactly once and returns to the start.
Key contrast with Eulerian:
- Eulerian: every edge once. Hamiltonian: every vertex once.
- Euler's theorem gives a simple degree condition. No simple condition exists for Hamiltonian — it's identified by inspection for small networks.
For a 4-vertex network A–B–C–D–A (square): Hamiltonian cycle = A→B→C→D→A. Uses every vertex once.
What to write in your book
- Hamiltonian path: visits every vertex exactly once, different start/end.
- Hamiltonian cycle: visits every vertex once, returns to start.
- No simple existence theorem — use inspection for small networks.
Worked examples · reveal each step
Network: A–B, B–C, C–D, D–A, A–C. Classify: (i) A→B→C→A→D (ii) A→C→B→C→D (iii) A→B→C→D
Network with degrees A=4, B=2, C=4, D=2, E=2. Does an Eulerian circuit exist?
Network: A–B, A–C, B–C, B–D, C–D, D–E. Find a Hamiltonian path from A to E.
- A network has vertex degrees 3, 2, 3, 2, 2. Does an Eulerian circuit exist? Does an Eulerian trail exist?
- Give an example of a trail that is NOT a path in a 4-vertex network. Draw the network and label the trail.
- A network has 5 vertices forming a complete graph (every pair connected). Does a Hamiltonian cycle exist? Find one.
- Explain in your own words why an Eulerian circuit requires all even degrees.
For the postman to walk every street exactly once and return: the network must be connected and every intersection must have even degree — 0 odd-degree vertices means an Eulerian circuit exists. If exactly 2 intersections have odd degree, an Eulerian trail exists (start at one odd vertex, end at the other).
Q1. A trail is best described as a walk in which:
Q2. An Eulerian circuit exists if and only if:
Q3. A connected network has vertex degrees 4, 4, 2, 2, 2. Which of the following is true?
Q4. A Hamiltonian path visits:
Q5. A network has vertex degrees 3, 3, 2, 2. An Eulerian trail (not circuit):
SA 1. A network has 6 vertices with degrees 4, 3, 3, 2, 2, 2. (a) Does an Eulerian circuit exist? (b) Does an Eulerian trail exist? Justify both answers. (2 marks)
SA 2. Explain the key difference between an Eulerian circuit and a Hamiltonian cycle. Give a network where an Eulerian circuit exists but a Hamiltonian cycle is impossible, and explain why. (3 marks)
Answers (click to reveal)
MC 1 — B: Trail = no repeated edges.
MC 2 — D: Connected + all even degrees → Eulerian circuit.
MC 3 — A: All degrees (4,4,2,2,2) are even → Eulerian circuit exists.
MC 4 — C: Hamiltonian = every vertex once.
MC 5 — B: Exactly 2 odd-degree vertices → Eulerian trail, starting/ending at those vertices.
SA 1: 2 odd-degree vertices [identify: degree-3 vertices] → (a) no circuit [1]; (b) yes trail [1].
SA 2: Clear distinction [1]; valid example [1]; explanation [1].
Timed questions on trails, Eulerian circuits and Hamiltonian paths.
⚔ Enter the arenaMark lesson as complete
Tick when you've finished the practice and review.